单调栈

739.每日温度

题意概括：找下一个比当前元素大的数

关键点

栈存的是下标
如果每次存的都是比栈顶小的元素，找的就是比当前元素大的数
如果每次存的都是比栈顶大的元素，找的就是比当前元素小的数
单调栈记录的是遍历过的元素，栈顶和当前元素对比，再进行求值的过程

详细版代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures){
        stack<int> st;
        vector<int> result(temperatures.size(),0);
        st.push(0);
        for(int i=1; i<temperatures.size(); i++)
        {
            if(temperatures[i]<temperatures[st.top()]){
                st.push(i);
            }else if(temperatures[i]==temperatures[st.top()]){
                st.push(i);
            }else{
                //将栈内比当前元素小的元素全部弹出之后再push当前元素
                while(!st.empty()&&temperatures[i]>temperatures[st.top()]){
                    result[st.top()]=i-st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

精简版代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> st; // 递增栈
        vector<int> result(T.size(), 0);
        for (int i = 0; i < T.size(); i++) {
            while (!st.empty() && T[i] > T[st.top()]) { // 注意栈不能为空
                result[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);

        }
        return result;
    }
};

496.下一个更大元素 I

题目链接

题意概括：相同的元素在另外一个数组找下一个更大元素

解题思路

先找nums2的下一个最大元素，存入result2数组。问题转化为为nums1中的每个下标找对应的result2元素。即是nums1下标->result2元素，解决方案为建立nums2的元素->nums2的下标，再通过result2[m[nums1[i]]访问result2的元素。

代码

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result2(nums2.size(),-1);
        for(int i=0; i<nums2.size(); i++)
        {
            while(!st.empty()&&nums2[i]>nums2[st.top()]){
                result2[st.top()]=nums2[i];
                st.pop();
            }
            st.push(i);
        }
        //映射麻烦,nums1下标->result2的结果
        //nums2元素->nums2下标 == nums2元素->result2下标 == nums1元素->result2下标
        //nums1元素->result2的下标->result2结果
        map<int,int> m;
        for(int i=0; i<nums2.size(); i++)
        {
            m[nums2[i]]=i;
        }
        vector<int> result1(nums1.size(),-1);
        for(int i=0; i<nums1.size(); i++)
        {
            result1[i]=result2[m[nums1[i]]];
        }
        return result1;
    }
};

503.下一个更大元素 II

题目链接

题目概述：找下一个更大元素，但是环形

思路1(开辟新数组)

// 版本一
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        // 拼接一个新的nums
        vector<int> nums1(nums.begin(), nums.end());
        nums.insert(nums.end(), nums1.begin(), nums1.end());
        // 用新的nums大小来初始化result
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;

        // 开始单调栈
        stack<int> st;
        st.push(0);
        for (int i = 1; i < nums.size(); i++) { 
            if (nums[i] < nums[st.top()]) st.push(i); 
            else if (nums[i] == nums[st.top()]) st.push(i);
            else { 
                while (!st.empty() && nums[i] > nums[st.top()]) {
                    result[st.top()] = nums[i];
                    st.pop();
                }
                st.push(i);
            }
        }
        // 最后再把结果集即result数组resize到原数组大小
        result.resize(nums.size() / 2);
        return result;
    }
};

思路2(取模)

// 版本二
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;
        stack<int> st;
        st.push(0);
        for (int i = 1; i < nums.size() * 2; i++) { 
            // 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
            if (nums[i % nums.size()] < nums[st.top()]) st.push(i % nums.size());
            else if (nums[i % nums.size()] == nums[st.top()]) st.push(i % nums.size()); 
            else {
                while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                    result[st.top()] = nums[i % nums.size()];
                    st.pop();
                }
                st.push(i % nums.size());
            }
        }
        return result;
    }
};

42.接雨水

题目链接

双指针

按列取雨水

当前列雨水面积：min(左边柱子的最高高度，右边柱子的最高高度) - 当前柱子高度。
从左往右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);
从右往左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0;
        vector<int> maxLeft(height.size(), 0);
        vector<int> maxRight(height.size(), 0);
        int size = maxRight.size();

        // 记录每个柱子左边柱子最大高度
        maxLeft[0] = height[0];
        for (int i = 1; i < size; i++) {
            maxLeft[i] = max(height[i], maxLeft[i - 1]);
        }
        // 记录每个柱子右边柱子最大高度
        maxRight[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            maxRight[i] = max(height[i], maxRight[i + 1]);
        }
        // 求和
        int sum = 0;
        for (int i = 0; i < size; i++) {
            int count = min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        return sum;
    }
};

按行取雨水

原理：找左边比当前元素大的数，找右边比当前元素大的数。

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0; // 可以不加
        stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度
        st.push(0);
        int sum = 0;
        for (int i = 1; i < height.size(); i++) {
            if (height[i] < height[st.top()]) {     // 情况一
                st.push(i);
            } if (height[i] == height[st.top()]) {  // 情况二
                st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。
                st.push(i);
            } else {                                // 情况三
                while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while
                    int mid = st.top();
                    st.pop();
                    if (!st.empty()) {
                        int h = min(height[st.top()], height[i]) - height[mid];
                        int w = i - st.top() - 1; // 注意减一，只求中间宽度
                        sum += h * w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};

84.柱状图中最大的矩形

题目链接

题目概要：找左边比当前元素小的元素，找右边比当前元素小的元素。

双指针

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> minLeftIndex(heights.size());
        vector<int> minRightIndex(heights.size());
        int size = heights.size();

        // 记录每个柱子 左边第一个小于该柱子的下标
        minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环
        for (int i = 1; i < size; i++) {
            int t = i - 1;
            // 这里不是用if，而是不断向左寻找的过程
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        // 记录每个柱子 右边第一个小于该柱子的下标
        minRightIndex[size - 1] = size; // 注意这里初始化，防止下面while死循环
        for (int i = size - 2; i >= 0; i--) {
            int t = i + 1;
            // 这里不是用if，而是不断向右寻找的过程
            while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];
            minRightIndex[i] = t;
        }
        // 求和
        int result = 0;
        for (int i = 0; i < size; i++) {
            int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            result = max(sum, result);
        }
        return result;
    }
};

单调栈

关键点

首尾加0
栈内每次存的都是比栈顶元素大的数