滑动窗口、双指针、单调队列、单调栈

滑动窗口、双指针、单调队列、单调栈

LeetCode. 32 最长有效括号

• 括号序列合法 <=> 所有前缀和 >= 0 且 cnt == 0
• start: 当前枚举的这一段的开头
• cnt: 前缀和
• ( = 1
• ) = -1
• 枚举过程中出现的情况：
  1. cnt < 0 : start = i + 1, cnt = 0;
  2. cnt > 0 : go on
  3. cnt == 0 : 符合条件，res = max(res, i - start + 1)
• 重点：对s正反各遍历一次，取其中的最大值

class Solution {
    
public:
    int work(string &s) {
    
        int res = 0;
        for(int i = 0, start = 0, cnt = 0; i < s.size(); ++i) {
    
            if(s[i] == '(') ++cnt;
            else --cnt;

            if(cnt < 0) start = i+1, cnt = 0;
            else if(cnt == 0) res = max(res, i - start + 1);
        }
        return res;
    }
    int longestValidParentheses(string s) {
    
        int ans1 = work(s);
        for(auto &c:s)
            c ^= 1;
        reverse(s.begin(), s.end());
        return max(ans1, work(s));
    }
};

LeetCode. 84 柱状图中最大的矩形

• 枚举所有柱形的上边界，作为整个矩形的上边界，然后求出左右边界

• 求左右边界：找出左边离它最近、比它小的柱形的位置left

  ​ 找出右边离它最近、比它小的柱形的位置right

class Solution {
    
public:
    int largestRectangleArea(vector<int>& heights) {
    
        int n = heights.size();
        vector<int> left(n), right(n);

        stack<int> stk;
        for(int i = 0; i < n; ++i) {
    
            while(stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
            if(stk.empty()) left[i] = -1;
            else left[i] = stk.top();
            stk.push(i);
        }
        while(stk.size()) stk.pop();
        for(int i = n - 1; i >= 0; --i) {
    
            while(stk.size() && heights[stk.top()] >= heights[i]) stk.pop();
            if(stk.empty()) right[i] = n;
            else right[i] = stk.top();
            stk.push(i);
        }

        int res = 0;
        for(int i = 0; i < n; ++i) {
    
            res = max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
    
};

LeetCode. 42 接雨水

class Solution {
    
public:
    int trap(vector<int>& height) {
    
        int res = 0;
        stack<int> stk;

        for(int i = 0; i < height.size(); ++i) {
    
            int last = 0;
            while(stk.size() && height[stk.top()] <= height[i]) {
    
                int t = stk.top();
                stk.pop();
                res += (height[t] - last) * (i - t - 1);
                last = height[t];
            }
            if(stk.size()) {
    
                res += (height[i] - last) * (i - stk.top() - 1);
            }
            stk.push(i);
        }
        return res;
    }
};

LeetCode. 239滑动窗口的最大值

class Solution {
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    
        vector<int> res;
        deque<int> q;
        for(int i = 0; i < nums.size(); ++i) {
    
            if(q.size() && i - k >= q.front()) q.pop_front();
            while(q.size() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            if(i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

LeetCode. 918 环形子数组的最大和

class Solution {
    
public:
    int maxSubarraySumCircular(vector<int>& nums) {
    
        int n = nums.size();
        for(int i = 0; i < n; ++i) nums.push_back(nums[i]);
        vector<int> s(2 * n + 1, 0);
        for(int i = 1; i < 2*n+1; ++i) s[i] = s[i-1] + nums[i-1];

        int res = INT_MIN;
        deque<int> q;
        q.push_back(0);
        for(int i = 1; i < 2*n+1; ++i) {
    
            if(q.size() && i - q.front() > n) q.pop_front();
            if(q.size()) res = max(res, s[i] - s[q.front()]);
            while(q.size() && s[q.back()] >= s[i]) q.pop_back();
            q.push_back(i);
        }
        return res;
    }
};