单调栈

通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了

739. 每日温度

维护一个栈顶到栈底递减的栈。

  • 当栈为空,或者遍历元素小于栈顶元素,遍历元素的索引入栈
  • 当遍历元素大于栈顶元素,说明找到了,值就是索引相减
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size(),0);
        stack<int> stk;
        for(int i=0; i<temperatures.size(); i++) {
            if(stk.empty()) {
                stk.push(i);
            } else {

                if(temperatures[i]< temperatures[stk.top()]) {
                    stk.push(i);
                } else {
                    while(!stk.empty() && temperatures[i]>temperatures[stk.top()]) {
                        ans[stk.top()] = i - stk.top();
                        stk.pop();
                    }
                    stk.push(i);
                }
            }
        }
        return ans;
    }
};

496. 下一个更大元素 I

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> umap;
        for(int i=0; i<nums1.size(); i++) umap[nums1[i]] = -1;
        stack<int> stk;
        for(int i=0; i<nums2.size(); i++) {
            if(stk.empty()) {
                stk.push(nums2[i]);
            } else {
                if( nums2[i] < stk.top() ) {
                    stk.push(nums2[i]);
                } else {
                    while(!stk.empty() &&  nums2[i] > stk.top() ) {
                        if(umap.find(stk.top())!=umap.end()) {
                            umap[stk.top()] = nums2[i];
                        }
                        stk.pop();
                    }
                    stk.push(nums2[i]);
                }
            }
        }
        vector<int> ans;
        for(int i=0; i<nums1.size();i++) {
            ans.push_back(umap[nums1[i]]);
        }
        return ans;
    }
};

503. 下一个更大元素 II

循环数组,模拟两遍遍历

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int size = nums.size();
        vector<int> ans(size, -1);
        stack<int> stk;  // 放索引
        // 模拟两遍遍历
        for(int i=0; i<size*2;i++) {
            if(stk.empty()) {
                stk.push(i%size);
            } else {
                if(nums[i%size] < nums[stk.top()]) {
                    stk.push(i%size);
                } 
                else {
                    while(!stk.empty() && nums[i%size] > nums[stk.top()]) {
                        ans[stk.top()] = nums[i%size];
                        stk.pop();
                    }
                    stk.push(i%size);
                }
            }
        }
        return ans;
    }
};

42. 接雨水

  • 【超时】双指针,每一列的左边的最大,右边的最高柱子,两个中较小的减去这一列的高度

    class Solution {
    public:
      int trap(vector& height) {
          int ans = 0;
          // 最左边和最右边都不加水
          for(int i=1; i height[l] ? lHeight : height[l];
              }
              for(int r=i+1; r height[r] ? rHeight : height[r];
              }
              int minHeight = min(lHeight, rHeight); // 去两边最小的
              int water = minHeight - height[i];
              if(water>0) ans+=water;  // 正的加上去
          }
          return ans;
      }
    };
  • 动态规划。上面的算法超时了,就是左边最大,右边最大都重复计算了,可以用两个数组维护

    class Solution {
    public:
      int trap(vector& height) {
          int ans = 0;
          vector leftMaxHeight(height.size(),0);
          vector rightMaxHeight(height.size(),0);
          leftMaxHeight[0] = height[0];
          rightMaxHeight[height.size()-1] = height[height.size()-1];
    
          // 获取最大的左右两个数组
          for(int i=1; i0; i--) {
              rightMaxHeight[i] = max(rightMaxHeight[i+1], height[i]);
          }
          // 遍历
          for(int i=1; i 0) ans+=water;
          }
          return ans;
      }
    };
  • 【使用行计算】单调栈,积水:低、高、低,所以栈顶最小;

    找到比当前索引大的第一个数,索引相减-1就是宽度,高度就是当前元素-栈顶第二元素

    class Solution {
    public:
      int trap(vector& height) {
          stack stk; // 递增栈,放索引
          int ans = 0;
          for(int i=0; iheight[stk.top()]) {
                      while(!stk.empty() && height[i] > height[stk.top()]){
                          int rightIndex = i; // 右边当前高的索引
                          int midIndex = stk.top();
                          stk.pop();
                          if(!stk.empty()) {
                              int leftIndex = stk.top(); // 左边高的索引
                              int h = min(height[rightIndex], height[leftIndex]) - height[midIndex];
                              int w = rightIndex - leftIndex - 1;
                              ans += h * w;
                          }
                      }
                      stk.push(i);
                  } else if(height[i] == height[stk.top()]) {
                      stk.pop();
                      stk.push(i);
                  } else {
                      stk.push(i);
                  }
              }
          }
          return ans;
      }
    };

84. 柱状图中最大的矩形

  class Solution {
  public:
      int largestRectangleArea(vector& heights) {
          stack stk;  // 维护递减栈,头最大
          // 需要在数组前后插入0,防止第一个元素和最后一个元素找不到左右
          heights.push_back(0);
          heights.insert(heights.begin(),0);
          int maxArea = 0;
          for(int i=0; i= heights[stk.top()]) {
                      stk.push(i);
                  } else {
                      while(heights[i] < heights[stk.top()]) {
                          // 当前top的最大面积就是top为索引起点的最大矩形
                          int mid = stk.top();
                          stk.pop();
                          int rightIndex = i;
                          int leftIndex = stk.top();
                          int w = rightIndex-leftIndex-1;
                          int h = heights[mid];
                          maxArea = max(maxArea, w*h);
                      }
                      stk.push(i);
                  }
              }
          }
          return maxArea;
      }
  };
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇