【代码随想录】二刷-单调栈

2023-05-13 14:33:13 浏览数 (2)

单调栈

739. 每日温度

代码语言：javascript复制
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& t) {
        stack<int>st;// 存下标
        int n = t.size();
        vector<int>ret(n,0);
        st.push(0);
        for(int i = 1; i < n;i  ){
            if(t[i] <= t[st.top()]){
                st.push(i);
            }else{// 找大更大的了
                // 可以简化为，去掉if else 只剩下方这块代码
                while(!st.empty() && t[i] > t[st.top()]){// 注意这里是一个循环，一直往前找
                    ret[st.top()] = i-st.top();//求得距离
                    st.pop();
                }
                // 没有更小的了，放入
                st.push(i);
            }
        }
        return ret; 
    }
};

496. 下一个更大元素 I

代码语言：javascript复制
// 求nums2中每个数右边第一个更大的数是什么，然后看这个数在不在nums1中，在，则将结果收集
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        // 求num1中的数在num2中，右侧第一个更大的数的是什么
        vector<int>ret(nums1.size(),-1);
        // 保存num1中数及所对应的下标，用于收集结果到ret中
        unordered_map<int,int>mp;
        for(int i = 0; i < nums1.size();i  ){
            mp[nums1[i]] = i;
        }
        stack<int>st;// 存nums2下标
        st.push(0);
        for(int i = 1; i < nums2.size();i  ){
            if(nums2[i] <= nums2[st.top()]){
                st.push(i);
            }else{
                while(!st.empty() && nums2[i] > nums2[st.top()]){
                    if(mp.count(nums2[st.top()]) > 0){// 1中存在这个数
                        int index = mp[nums2[st.top()]];
                        ret[index] = nums2[i];
                    }
                    // 注意无论是否在num1中都要pop出来
                    st.pop();
                }
                st.push(i);
            }
        }
        return ret;
    }
};

503. 下一个更大元素 II

代码语言：javascript复制
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int>nums1(nums.begin(),nums.end());
        // 复制一份nums拼接到尾部
        nums.insert(nums.end(),nums1.begin(),nums1.end());
        vector<int>ret(nums.size(),-1);
        if(nums.size() == 0)return  ret;
        stack<int>st;
        for(int i = 0; i < nums.size(); i  ){
            while(!st.empty() && nums[i] > nums[st.top()]){
                ret[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        ret.resize(nums.size()/2);// 去掉多余的
        return ret;
    }
};

  • 或，直接走两遍nums
代码语言：javascript复制
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        stack<int>st;
        vector<int>ret(n,-1);
        if(n == 0)return ret;
        for(int i = 0; i < n*2;i  ){
            while(!st.empty() && nums[i % n] > nums[st.top()]){
                ret[st.top()] = nums[i % n];
                st.pop();
            }
            st.push(i % n);
        }
        return ret;
    }
};

42. 接雨水

代码语言：javascript复制
class Solution {
public:
    int trap(vector<int>& height) {
        // 找每个柱子左右两边第一个大于该柱子高度的柱子
        int n = height.size();
        int ret = 0;
        stack<int>st;
        st.push(0);
        for(int i = 1; i < n ;i  ){
            if(height[i] < height[st.top()]){
                st.push(i);
            }else if(height[i] == height[st.top()]){// 相同的更新边界,相当于合并区间
                st.pop();// 加不加都可，但是处理相同情况的思想不同，这里略
                st.push(i);
            }else{// 大于左边界，即找到右边界
                while(!st.empty() && height[i] > height[st.top()]){
                    int mid = height[st.top()];// 当做底
                    st.pop();
                    if(!st.empty()){
                        // 选取小的计算高度
                        int h = min(height[i],height[st.top()])-mid;
                        // 宽度
                        int w = i - st.top() - 1;
                        ret  = h * w;
                    }
                }
                st.push(i);
            }
        }
        return ret;
    }
};

  • 精简版
代码语言：javascript复制
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int ret = 0;
        stack<int>st;
        st.push(0);
        for(int i = 1; i < n ;i  ){
            while(!st.empty() && height[i] > height[st.top()]){
                    int mid = height[st.top()];// 当做底
                    st.pop();
                    if(!st.empty()){
                        // 选取小的计算高度
                        int h = min(height[i],height[st.top()])-mid;
                        // 宽度
                        int w = i - st.top() - 1;
                        ret  = h * w;
                    }
            }
            st.push(i);
        }
        return ret;
    }
};

84. 柱状图中最大的矩形

代码语言：javascript复制
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {

        // 找到每个数的，左边第一个更小的，右边第一个更小的,找雨水相反找两边更大的
        // 计算面积为，这个数的值为高，右边第一个小的到它的距离为宽，依次求得面积
        // 实际的面积大小就是一个数以及它与它右边第一个数中间可覆盖的面积
        // 例如示例1中的值5到2，先计算出6的，6x1=2,然后计算5的5x()
        
        // 左右填充0为了每个值都能找到左右更小的
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        stack<int>st;
        st.push(0);
        int ret = 0;
        for(int i = 1; i < heights.size() ;i  ){
            if(heights[i] > heights[st.top()]){
                st.push(i);
            }else if(heights[i] == heights[st.top()]){// 相等向右合并
                st.pop();
                st.push(i);
            }else{
                // 判断小于栈顶的元素 和 栈顶元素，以及栈顶元素下一位，求得所有计算需要的值
                while(!st.empty() && heights[i] < heights[st.top()]){
                    int h = heights[st.top()];// 高
                    st.pop();
                    if(!st.empty()){
                        int left = st.top();
                        int right = i;
                        int w =  right-left-1;
                        ret = max(ret,w*h);
                    }
                }
                st.push(i);// 放入的时候满足大于栈顶元素
            }
        }
        return ret;
    }
};

  • 精简版
代码语言：javascript复制
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        stack<int>st;
        st.push(0);
        int ret = 0;
        for(int i = 1; i < heights.size() ;i  ){
            while(!st.empty() && heights[i] < heights[st.top()]){
                    int h = heights[st.top()];// 高
                    st.pop();
                    if(!st.empty()){
                        int left = st.top();
                        int right = i;
                        int w =  right-left-1;
                        ret = max(ret,w*h);
                    }
            }
            st.push(i);
        }
        return ret;
    }
};

  • 至此，代码随想录二刷完成。
height int push size vector

0 人点赞