【leetcode hot 100 739】每日温度

解法一：暴力解法

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n=temperatures.length;   // 指向要找下一个更高温度的地方int[] result = new int[n];for(int left=0;left<n;left++){int right=left+1;  // 指向正在找最高温度的地方while(right<n){if(temperatures[left]<temperatures[right]){result[left]=right-left;break;}else{right++;}}}return result;}
}

错误原因：

解法二：单调栈

• 当 i=0 时，单调栈为空，因此将 0 进栈。

  • stack=[0(73)]

  • ans=[0,0,0,0,0,0,0,0]

• 当 i=1 时，由于 74 大于 73，因此移除栈顶元素 0，赋值 ans[0]:=1−0，将 1 进栈。

  • stack=[1(74)]

  • ans=[1,0,0,0,0,0,0,0]

• 当 i=2 时，由于 75 大于 74，因此移除栈顶元素 1，赋值 ans[1]:=2−1，将 2 进栈。

  • stack=[2(75)]

  • ans=[1,1,0,0,0,0,0,0]

• 当 i=3 时，由于 71 小于 75，因此将 3 进栈。

  • stack=[2(75),3(71)]

  • ans=[1,1,0,0,0,0,0,0]

• 当 i=4 时，由于 69 小于 71，因此将 4 进栈。

  • stack=[2(75),3(71),4(69)]

  • ans=[1,1,0,0,0,0,0,0]

• 当 i=5 时，由于 72 大于 69 和 71，因此依次移除栈顶元素 4 和 3，赋值 ans[4]:=5−4 和 ans[3]:=5−3，将 5 进栈。

  • stack=[2(75),5(72)]

  • ans=[1,1,0,2,1,0,0,0]

• 当 i=6 时，由于 76 大于 72 和 75，因此依次移除栈顶元素 5 和 2，赋值 ans[5]:=6−5 和 ans[2]:=6−2，将 6 进栈。

  • stack=[6(76)]

  • ans=[1,1,4,2,1,1,0,0]

• 当 i=7 时，由于 73 小于 76，因此将 7 进栈。

  • stack=[6(76),7(73)]

  • ans=[1,1,4,2,1,1,0,0]

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length; // 指向要找下一个更高温度的地方int[] result = new int[n];Deque<Integer> stack = new LinkedList<>();for (int i = 0; i < n; i++) {while(!stack.isEmpty() && temperatures[i]>temperatures[stack.peek()]){int temp = stack.pop();result[temp] = i-temp;}stack.push(i);}return result;}
}