代码随想录第46期 单调栈

这道题主要是单调栈的简单应用

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> result(T.size(),0);
        stack<int> st;
        st.push(0);
        for(int i=1;i<T.size();i++){
            if(T[i]<=T[st.top()]){
                st.push(i);
            }else{
                while(!st.empty()&&T[i]>T[st.top()]){
                    result[st.top()]=i-st.top();
                    st.pop();
                }
                st.push(i);



            }
        }
        return result;
    }
};

暴力模拟

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        for(int i=0;i<nums1.size();i++){
            int j=0;
            while(nums1[i]!=nums2[j]){
                j++;
            }
            while(j<nums2.size()&&nums1[i]>=nums2[j]){
                j++;
            }
            if(j>=nums2.size()){
                result.push_back(-1);
            }else{
                int val=nums2[j];
                result.push_back(val);
            }
        }
        return result;
    }
};

单调栈

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result(nums1.size(),-1);
        stack<int> st;
         st.push(0);
          unordered_map<int, int> umap; // key:下标元素，value：下标
        for (int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }
        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 (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
                        int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
                        result[index] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }



        }
     
        return result;
    }
};

比上一题多了个处理循环的操作

可以是模拟循环

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(),-1);
        stack<int> st;
        st.push(0);
        for(int i=1;i<nums.size()*2;i++){
            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());
            }
        }
          // 最后再把结果集即result数组resize到原数组大小
        result.resize(nums.size());
        return result;
    }
};

也可以是直接扩充数组

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> nums1(nums.begin(), nums.end());
        nums.insert(nums.end(), nums1.begin(), nums1.end());
        vector<int> result(nums.size(),-1);
        stack<int> st;
        st.push(0);
        unordered_map<int,int> umap;
        for(int i=0;i<nums.size();i++){
            if(nums[i]<=nums[st.top()]){
                st.push(i);
            }else{
            
                while(!st.empty()&&nums[i]>nums[st.top()]){
                        result[st.top()]=nums[i];
                        umap[st.top()]=nums[i];
                        st.pop();
                }
                st.push(i);
            }
        }
          // 最后再把结果集即result数组resize到原数组大小
        result.resize(nums.size() / 2);
        return result;
    }
};

这道题同样是一个双指针问题

class Solution {
public:
    int trap(vector<int>& nums) {
// max(min{左max,右max}-arr[i]，0)
//预处理最大值  left:0-0最大值  0-1最大 0-i最大值
//          right:12-12最大值，11-12最大值 i-12最大值
/*int n=height.size();
int *lmax=new int[n];
int *rmax=new int[n];
lmax[0]=height[0];
for(int i=1;i<n;i++){
lmax[i]=max(lmax[i-1],height[i]);
}
rmax[n-1]=height[n-1];
for(int i=n-2;i>=0;i--){
rmax[i]=max(rmax[i+1],height[i]);
}
int ans=0;
for(int i=1;i<n-1;i++){
    ans+=max(0,min(lmax[i-1],rmax[i+1])-height[i]);
}

return ans;*/
int l=0,r=nums.size()-1,lmax=nums[0],rmax=nums[nums.size()-1];
int ans=0;
while(l<=r){
if(lmax<=rmax){
    ans+=max(0,lmax-nums[l]);
    
    lmax=max(lmax,nums[l]);l++;
}else{
      ans+=max(0,rmax-nums[r]);
     
    rmax=max(rmax,nums[r]); r--;
}

}
return ans;
    }




    
};

与上一题类似，但是更麻烦些

双指针解法

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;
    }
};

单调栈解法

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result = 0;
        stack<int> st;
        heights.insert(heights.begin(), 0); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素0
        st.push(0);

        // 第一个元素已经入栈，从下标1开始
        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()]) { // 注意是while
                    int mid = st.top();
                    st.pop();
                    if (!st.empty()) {
                        int left = st.top();
                        int right = i;
                        int w = right - left - 1;
                        int h = heights[mid];
                        result = max(result, w * h);
                    }
                }
                st.push(i);
            }
        }
        return result;
    }
};