Skip to content

Latest commit

 

History

History
352 lines (314 loc) · 11.9 KB

T8-单调栈技巧.md

File metadata and controls

352 lines (314 loc) · 11.9 KB
Raw

单调栈技巧

42. 接雨水 [Hard] [*]

  • 当前位置的盛水量取决于左侧/右侧相对最高位置的比较情况
  • 使用双指针法，每次更新左/右当前的最高位置，取最低位置计算结果
    • 本质上将，当前位置的接水量取决于当前位置左右的最高点
    • 双指针法简化了重复求每个位置左右最高点的计算过程
  • 时间复杂度 O(N)
  • 关键点 单调栈
class Solution {
public:
    int trap(vector<int>& height) {
        int l_max = 0;
        int r_max = 0;
        int left = 0;
        int right = height.size() - 1;
        int ans = 0;
        while (left <= right) {
            l_max = max(l_max, height[left]);
            r_max = max(r_max, height[right]);
            if (r_max < l_max) {
                ans += (r_max - height[right]);
                right--;
            }
            else {
                ans += (l_max - height[left]);
                left++;
            }
        }
        return ans;
    }
};

84. 柱状图中的最大面积

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积

  • 最朴素的思路： 对于每个柱子：找到左右边界得到宽度，然后计算最大面积
  • 在此思路上进行优化：如何寻找左右边界：
    • 通过单调递增栈来搜索：当小于栈顶值时进行出栈操作，栈顶元素对应的左右边界可以通过当前新入栈的元素（右边界）以及，栈顶元素的下一个元素(左边界)得到；进而更新值
    • 特殊情况： 当出栈后栈空时，需要做特殊处理； 最左侧添加0即可
    • 特殊情况2: 如果柱状图天然为递增情况，那么不会有出栈的情况，这种情况下：最右侧添加0即可
  • 关键点： 单调栈 数组预处理
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(), 0); // 
        heights.push_back(0); // 
        int n = heights.size();
        stack<int> st;
        int res = 0;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && heights[st.top()] > heights[i]) {
                int cur = st.top();
                st.pop();
                int left = st.top() + 1; // 精髓
                int right = i - 1;
                // cout << cur << "-" << heights[cur] << " " << (right - left + 1) << " - " << (right - left + 1) * heights[cur] << endl;
                res = max( (right - left + 1) * heights[cur], res); 
                //cout << left << " "<< right << endl;
            }
            st.push(i);
        }
        return res;
    }
};

85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积

  • 与最大正方形相比，计算矩形的面积更为复杂，使用动态规划方法做起来难度陡增
  • 本题更为简单直接的解法为结合[LC84.柱状图的最大面积]将问题做转换
    • 对于矩阵每行都可以得到相应的高度信息，从而使用单调栈得到当前行对应的最大面积；
    • 时间复杂度: O(mn) 空间复杂度 O(n)
    • 理解起来比较简单易懂 avtar
  • 关键点： 问题转换 单调栈
class Solution {
public:
    int largestRectangleArea(vector<int> heights) {
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int ans = 0;
        stack<int> st;
        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int cur = st.top();
                st.pop();
                int left = st.top() + 1; // 左边界
                int right = i - 1;  // 右边界
                ans = max(ans, heights[cur] * (right - left + 1));
            }
            st.push(i);
        }
        //cout << ans << endl;
        return ans;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<int> heights(cols);
        int ans = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                }
                else {
                    heights[j] = 0;
                }
            }
            ans = max(ans, largestRectangleArea(heights));
        }
        return ans;
    }
};

402. 移除K个字符 [Medium]

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219

class Solution {
public:
    string removeKdigits(string num, int k) {
        vector<char> st;
        int remain = num.size() - k;
        for (int i = 0; i < num.size(); i++) {
            //单调栈
            while (k && !st.empty() && num[i] < st.back()) {
                st.pop_back();
                k-=1;
            } 
            st.push_back(num[i]);
        }
        string ans = "";
        bool flag = false;
        for (int i = 0; i < remain; i++) {
            if (!flag && st[i] == '0')
                continue;
            ans.push_back(st[i]);
            flag = true;
        }
        return ans.empty() ? "0" : ans;
    }
};

456. 132模式

132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] , 判断序列中是否存在132模式

  • 主要寻找nums[i] < nums[k] < nums[j]
  • 依靠单调栈进行，通过递增单调栈，确定峰值nums[k]和nums[j],
  • 在寻找nums[i]时判断其小于历史栈顶元素即可 (第二大数)
  • 上述遍历过程要通过逆序遍历实现，因为132，那么相对来说确定3和2后判断1比较容易。
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> st;
        int k = INT_MIN;
        int n = nums.size(); 
        // i < j < k  
        // nums[i] < nums[k] < nums[j]
        for (int i = n - 1; i >= 0; i--) {
           // 发现1 
            if (nums[i] < k) return true;
            while (!st.empty() && st.top() < nums[i]) {
                // 记录2
                k = max(k, st.top());
                st.pop();
            }
            // 记录3
            st.push(nums[i]);
        }
        return false;
    }
};

补充. 求区间最小数乘区间和的最大值

https://mp.weixin.qq.com/s/UFv7pt_djjZoK_gzUBrRXA 给定一个数组，要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：区间中的最小数 * 区间所有数的和。

输入
3
6 2 1
输出
36
解释：满足条件区间是[6] = 6 * 6 = 36;
  • 暴力解法： 遍历一遍数组，寻找每个元素的左右边界，即找到小于当前元素的左右边界，构成区间。
    • 利用单调栈(递增栈)进行优化，将查找速度优化为O(1),与[LC84.柱状图中最大的矩形]做法一致。
  • 技巧性： 合理构造栈 前置和后置位填0
  • 时间复杂度 O(N)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int N = 500000+10;
int a[N];
int dp[N];
int main() {
    stack<int> st;
    int n, res = 0;
    cin >> n;
    // 处理边界问题 前后加0
    a[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[n+1] = 0;

    // 计算前缀和 前置为0
    int pre = 0;
    for (int i = 0; i <= n + 1; i++) {
        dp[i] = pre + a[i];
        pre = dp[i];
    }
    for (int i = 0; i <= n; i++) {
        while (!st.empty() && a[st.top()] > a[i]) {
            int peak = a[st.top()];
            st.pop();
            int left = a[st.top()];
            int lens = dp[i-1] - dp[left];
             
            res = max(res, lens*peak);
        }
        st.push(i);
    }
    cout << res << endl;
    return res;
}

496. 下一个更大元素 I

两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1

  • next greater 问题
  • 一般使用单调栈进行解决 [LC739.每日温度]解题一致
    • 从栈底到栈顶单调递减单调递减栈；单调栈保存数组索引，当遇到比当前栈顶元素大的值时进行出栈操作，并更新结果
    • 本题涉及两个数组，需要使用哈希表来进行一个结果索引的映射
  • 时间复杂度 O(N) 空间复杂度 O(N)
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map1;
        stack<int> st;
        vector<int> res(nums1.size(),-1);
        for (int i = 0; i < nums1.size(); i++) {
            map1[nums1[i]] = i;
        }
    
        for (int i = 0; i < nums2.size(); i++) {
            while (!st.empty() && nums2[st.top()] < nums2[i]) {
                if (map1.count(nums2[st.top()]) > 0) {
                    int index = map1[nums2[st.top()]];
                    res[index] = nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};

503. 下一个更大元素 II

一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

输入: [1,2,1]
输出: [2,-1,2]
  • 与[LC496]的主要区别在于循环数组，使得元素可以双向对比
  • 对该题进行简单转换，将数组进行二倍展开，使得每个元素可以与右侧元素进行重复对比；
    • 使用取模操作进行元素拓展访问
    • 只需要添加一点小改动即可
  • 时间复杂度 O(N) 空间复杂度 O(N)
  • 关键点： 单调栈 + 循环数组访问
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        stack<int> st;
        int n = nums.size();
        // 对循环数组进行展开， 通过取模操作进行循环访问
        for (int i = 0; i < 2*n; i++) {
            while (!st.empty() && nums[st.top()] < nums[i % n]) {
                res[st.top()] = nums[i % n];
                st.pop();
            }
            st.push(i%n);
        }
        return res;
    }
};