【leetcode】【剑指offer Ⅱ】038. 每日温度

问题描述：

• 请根据每日气温列表 temperatures，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。
  • 如果气温在这之后都不会升高，请在该位置用 0 来代替。

核心思路：

• 单调栈解题，找到数组每一个数下一个更大值的位置。
• 单调栈模板分为两种，从前往后遍历和从后往前遍历。
  • 从前往后的代码模板中，维护一个单调递减的栈，将当前数值与栈顶比较，如果当前数值更大，则栈顶元素的下一个更大值便找到了；此时便弹出栈顶并记录栈顶的下一个更大值。
  • 从后往前的代码模板中，同样是维护一个单调递减的栈，此时情况变了，栈顶元素会变成当前值的下一个更大值。

代码实现：

• 从前往后遍历代码实现如下：

  class Solution
  {
  public:
      vector<int> dailyTemperatures(vector<int>& temperatures)
      {
          stack<int> stk;
          vector<int> ans(temperatures.size());
          for(int i = 0; i < temperatures.size(); ++i)
          {
              while(!stk.empty() and temperatures[i] > temperatures[stk.top()])
              {
                  ans[stk.top()] = i - stk.top();
                  stk.pop();
              }
              stk.push(i);
          }
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

• 从后往前遍历代码实现如下：

  class Solution
  {
  public:
      vector<int> dailyTemperatures(vector<int>& temperatures)
      {
          int m = temperatures.size();
          vector<int> ans(m);
          stack<int> stk;
          for(int i = m-1; i >= 0; --i)
          {
              while(!stk.empty() and temperatures[i] >= temperatures[stk.top()])
                  stk.pop();
              ans[i] = stk.empty() ? 0 : stk.top()-i;
              stk.push(i);
          }
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18