lc1574

用栈可以维护单增序列，但是怎么样去找这个删除的最短子序列呢

• 找最长前缀非递减序列、最长后缀非递减序列
• 再用双指针找二者最优拼接点(因为想最小可能的删除，所以存在双指针的单调性)

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();
        if (n <= 1) return 0;
        
        // 步骤1：找最长前缀非递减序列的结束位置left
        int left = 0;
        while (left + 1 < n && arr[left] <= arr[left + 1]) {
            left++;
        }
        if (left == n - 1) return 0; // 整个数组已非递减
        
        // 步骤2：找最长后缀非递减序列的起始位置right
        int right = n - 1;
        while (right - 1 >= 0 && arr[right - 1] <= arr[right]) {
            right--;
        }
        
        // 步骤3：初始候选答案（只保留前缀或只保留后缀的情况）
        int ret = min(n - left - 1, right);
        
        // 步骤4：双指针找前缀和后缀的最优拼接点
        int i = 0, j = right;
        while (i <= left && j < n) {
            if (arr[i] <= arr[j]) {
                // 可以拼接，更新答案
                ret = min(ret, j - i - 1);
                i++;
            } else 
                j++;
        }
        
        return ret;
    }
};
 

 

lc1673

定长栈

+剩余数的条件三判断 保障了k长

while (!st.empty() && x < st.back() && st.size() + nums.size() - i > k)                 st.pop_back();

 class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        vector<int> st;
        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            while (!st.empty() && x < st.back() && st.size() + nums.size() - i > k) {
                st.pop_back();
            }
            if (st.size() < k) 
                st.push_back(x);
            
        }
        return st;
    }
};

 

 

lc865

（DFS）计算节点深度

若左右子树深度相同，当前节点即为最深叶子的最近公共祖先（LCA）；

否则取深度更深的子树的LCA

pair<TreeNode*,int> dfs(TreeNode* root,int depth)

 

亮点：pair dfs

出口!

auto left记录下一层拿到的结果，再去进行return if-else比较，确定return what

class Solution {

public:

    TreeNode* subtreeWithAllDeepest(TreeNode* root){

        return dfs(root,0).first;

    }

 

    //还和深度有关 维护一个pair

    pair<TreeNode*,int> dfs(TreeNode* root,int depth)

    {

        //出口 空节点

        if(!root)

            return {nullptr,depth-1};

        

        auto left=dfs(root->left,depth+1);

//1 catch return left

        auto right=dfs(root->right,depth+1);

 

        //返回控制

        if(!root->left && !root->right)

            return {root,depth};

        

        // 比较左右子树深度

        if(left.second == right.second) 

            return {root, left.second}; 

//2 battle = return  root,dep

 

        else if(left.second > right.second)

            return left;   

//3 !＝已完成 继承return longer             

        else 

            return right;               

    }

};

 

lcr44

class Solution {
public:
    vector<int> largestValues(TreeNode* root)
    {
        if(!root) return {};
        vector<int> ret;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size())
        {
            int sz=q.size();
            int mx=INT_MIN;
            while(sz--)
            {
                auto t=q.front();
                q.pop();
                mx=max(mx,t->val);
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            ret.push_back(mx);
        }
        return ret;
    }
};