739.每日温度，单调递减栈

linwt · linwt · commit 81dc8f790488 · 2022-04-04T11:34:23.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -95,6 +95,7 @@
 712. 两个字符串的最小ASCII删除和
 714. 买卖股票的最佳时机含手续费
 718. 最长重复子数组
+739. 每日温度
 1020. 飞地的数量
 1035. 不相交的线
 1143. 最长公共子序列
diff --git a/leetcode_Java/Solution0084.java b/leetcode_Java/Solution0084.java
@@ -42,15 +42,20 @@ public int largestRectangleArea(int[] heights) {
 /*
 单调栈
 1、单调栈分为单调递增栈和单调递减栈
-  1)单调递增栈即栈内元素保持单调递增的栈
-  2)同理单调递减栈即栈内元素保持单调递减的栈
+  1)单调递增栈，即栈内元素保持单调递增的栈
+  2)单调递减栈，即栈内元素保持单调递减的栈
 2、操作规则（下面都以单调递增栈为例）
   1)如果新元素比栈顶元素大，就入栈
   2)如果新元素比栈顶元素小，那就一直把栈顶元素弹出来，直到栈顶元素比新元素小，然后新元素入栈
 3、规则效果（举例：栈[1, 5, 6]，新元素2）
-(1)栈内的元素是递增的
-(2)当元素出栈时，这个新元素是出栈元素向右找第一个比它小的元素（2是6右边第一个比它小的元素）
-(3)当元素出栈后，新栈顶元素是出栈元素向左找第一个比它小的元素（5是6左边第一个比它小的元素）
+  1)栈内的元素是递增的
+  2)当元素出栈时，这个新元素是出栈元素向右找第一个比它小的元素（2是6右边第一个比它小的元素）
+  3)当元素出栈后，新栈顶元素是出栈元素向左找第一个比它小的元素（5是6左边第一个比它小的元素）
+4、使用单调栈的场景
+  1)需要查找数组每个元素左或右边第一个比它大或小的元素和索引时，可以用单调栈
+  2)利用栈存放索引，这样既可以通过索引获取索引差值，也可以通过索引从数组获取元素值
+  3)查找第一个比它大的元素时，用单调递减栈。因为新元素比它小时会入栈，形成单调递减栈，比它大时会出栈。
+  4)查找第一个比它小的元素时，用单调递增栈。因为新元素比它大时会入栈，形成单调递增栈，比它小时会出栈。
  */
 
 
@@ -71,9 +76,7 @@ public int largestRectangleArea(int[] heights) {
         int res = 0;
         int n = heights.length;
         int[] newHeights = new int[n + 2];
-        for (int i = 0; i < n; i++) {
-            newHeights[i + 1] = heights[i];
-        }
+        System.arraycopy(heights, 0, newHeights, 1, n);
         Deque<Integer> stack = new ArrayDeque<>();
         for (int right = 0; right < n + 2; right++) {
             while (!stack.isEmpty() && newHeights[right] < newHeights[stack.peek()]) {
diff --git a/leetcode_Java/Solution0739.java b/leetcode_Java/Solution0739.java
@@ -0,0 +1,48 @@
+// 739. 每日温度
+
+
+/*
+暴力：两层for循环遍历数组，查找每个元素右边第一个比它大的元素，计算索引差得到天数i，即为日期left在第i天之后才会有更高的温度
+ */
+class Solution {
+    public int[] dailyTemperatures(int[] temperatures) {
+        int n = temperatures.length;
+        int[] res = new int[n];
+        for (int left = 0; left < n - 1; left++) {
+            for (int right = left + 1; right < n; right++) {
+                if (temperatures[left] < temperatures[right]) {
+                    res[left] = right - left;
+                    break;
+                }
+            }
+        }
+        return res;
+    }
+}
+
+
+/*
+单调递减栈：
+1、查找每个元素右边第一个比它大的元素，可以利用单调递减栈的特性
+2、利用栈存放索引，这样既可以通过索引差获取天数，也可以通过索引从数组获取温度值
+3、遍历数组
+  1）栈为空 或 当前温度不大于栈顶温度，则当前索引入栈
+  2）栈不为空 且 当前温度大于栈顶温度，则弹出栈顶索引作为日期左边界，当前索引作为日期右边界，计算日期相差天数i，得到出栈索引日期在第i天之后才会有更高的温度。
+    循环弹出处理，当前温度不大于新栈顶温度，最后当前索引入栈，保证了栈内元素单调递减
+4、剩余栈不为空，说明部分日期后没有更高的温度，天数统一为0，由于数组初始化默认值为0，所以不用处理
+ */
+class Solution {
+    public int[] dailyTemperatures(int[] temperatures) {
+        int n = temperatures.length;
+        int[] res = new int[n];
+        Deque<Integer> stack = new ArrayDeque<>();
+        for (int right = 0; right < n; right++) {
+            while (!stack.isEmpty() && temperatures[right] > temperatures[stack.peek()]) {
+                int left = stack.pop();
+                res[left] = right - left;
+            }
+            stack.push(right);
+        }
+        return res;
+    }
+}
