【代码随想录】刷题笔记Day55

前言

• 周三，又到了为组会焦虑的日子，此为近忧，而找工作乃远虑啊，争取继续刷完~

739. 每日温度 - 力扣（LeetCode）

• 什么时候用单调栈
  • 一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置
• 问题本质
  • 用栈来记录遍历过的元素，达到空间换时间的效果
• 存放元素
  • 存下标i，方便计算差值，需要比较时T[i]读取
• 大小顺序
  • 右边第一个大/小，则从栈头到栈底，单调递增/减
• 具体过程看题解视频，做的非常清晰

• class Solution {
  public:
      vector<int> dailyTemperatures(vector<int>& temperatures) {
          int len = temperatures.size();
          stack<int> st;  // 递增栈
          st.push(0);  // 存下标
          vector<int> res(len, 0);  // 存结果
          for(int i = 1; i < len; i++){
              if(temperatures[i] <= temperatures[st.top()]){
                  st.push(i);
              }else{
                  while(!st.empty() && temperatures[i] > temperatures[st.top()]){  // 非空
                      res[st.top()] = i - st.top();
                      st.pop();
                  }
                  st.push(i);  // 栈为空或不大了就压入
              }
          }
          return res;
      }
  };

496. 下一个更大元素 I - 力扣（LeetCode）

• 暴力法

  • 遍历两个数组，找最大数，能通过

  • class Solution {
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
            int len1 = nums1.size();
            int len2 = nums2.size();
            vector<int> res(len1, -1);
            for(int i = 0; i < len1; i++){         // 遍历数组1
                for(int j = 0 ; j < len2; j++){    // 遍历数组2
                    if(nums1[i] == nums2[j]){      // 找到相同的数
                        for(int j2 = j + 1; j2 < len2; j2++){  // 往后找第一个大的数
                            if(nums2[j2] > nums2[j]){
                                res[i] = nums2[j2];
                                break;
                            }
                        }
                    }
                }
            }
            return res;
        }
    };

• 单调栈

  • 哈希记录nums1下标，递增单调栈遍历nums2，存元素更方便（根据题意）

  • class Solution {
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
            vector<int> res(nums1.size(),-1);  // 结果
            unordered_map<int, int> mp;   // 哈希
            stack<int> st;  // 递增栈
            st.push(nums2[0]);
            for(int i = 0; i < nums1.size(); i++) mp[nums1[i]] = i;
            if(nums2.size() == 1) return res;
            // 单调栈处理（存放元素）
            for(int i = 1; i < nums2.size(); i++){
                if(nums2[i] <= st.top()){
                    st.push(nums2[i]);
                }else{
                    while(!st.empty() && nums2[i] > st.top()){
                        // 全部处理，找到nums1的数就加入结果
                        if(mp.find(st.top()) != mp.end()){ // 用mp.count(st.top())>0也行
                            res[mp.find(st.top())->second] = nums2[i];
                        }
                        st.pop();
                    }
                    st.push(nums2[i]);
                }
            }
            return res;
        }
    };

503. 下一个更大元素 II - 力扣（LeetCode）???????

• ?环形的遍历两轮即可（不用扩充数组），递增单调栈，存下标

• class Solution {
  public:
      vector<int> nextGreaterElements(vector<int>& nums) {
          int len = nums.size();
          stack<int> st;
          vector<int> res(len,-1);
          if(len == 1) return res;
          st.push(0);
          for(int i = 1; i < len * 2; i++){
              int i2 = i % len;  // 遍历两轮
              if(nums[i2] <= nums[st.top()]){
                  st.push(i2);
              }else{
                  while(!st.empty() && nums[i2] > nums[st.top()]){
                      res[st.top()] = nums[i2];
                      st.pop();
                  }
                  st.push(i2);
              }
          }
          return res;
      }
  };

后言

• ?假期学校断了好几次电，干扰我刷题了→.→，还好CSDN和力扣能自动保存草稿，不然就吐血了。明天回家前正好可以把单调栈搞完~