503.下一个更大元素II，单调递减栈

linwt · linwt · commit 61e87f41634a · 2022-04-04T19:12:35.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -81,6 +81,7 @@
 491. 递增子序列
 494. 目标和
 496. 下一个更大元素 I
+503. 下一个更大元素 II
 509. 斐波那契数
 516. 最长回文子序列
 518. 零钱兑换 II
diff --git a/leetcode_Java/Solution0496.java b/leetcode_Java/Solution0496.java
@@ -30,17 +30,18 @@ public int[] nextGreaterElement(int[] nums1, int[] nums2) {
 
 /*
 单调递减栈：
-1、从右到左遍历nums2数组，获取每个元素的下一个更大元素
-  1）栈不为空 且 当前元素大于等于栈顶元素，则栈顶元素出栈，循环处理，直到当前元素小于栈顶元素，那么栈顶元素就是当前元素的下一个更大元素
+1、栈存放的是元素，因为用不到索引。nums1才需要索引来映射到结果数组
+2、从右到左遍历nums2数组，获取每个元素的下一个更大元素
+  1）栈不为空 且 当前元素大于栈顶元素，则栈顶元素出栈，循环处理，直到当前元素小于栈顶元素，那么栈顶元素就是当前元素的下一个更大元素
   2）记录当前元素的下一个更大元素到map中，当前元素入栈
-2、遍历nums1数组，直接从map中获取当前元素的下一个更大元素，存入结果数组，返回结果
+3、遍历nums1数组，直接从map中获取当前元素的下一个更大元素，存入结果数组，返回结果
  */
 class Solution {
     public int[] nextGreaterElement(int[] nums1, int[] nums2) {
         Map<Integer, Integer> map = new HashMap<>();
         Deque<Integer> stack = new ArrayDeque<>();
         for (int i = nums2.length - 1; i >= 0; i--) {
-            while (!stack.isEmpty() && nums2[i] >= stack.peek()) {
+            while (!stack.isEmpty() && nums2[i] > stack.peek()) {
                 stack.pop();
             }
             map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
@@ -53,4 +54,32 @@ public int[] nextGreaterElement(int[] nums1, int[] nums2) {
         }
         return res;
     }
+}
+
+
+/*
+单调递减栈：
+1、栈存放的是元素，因为用不到索引。nums1才需要索引来映射到结果数组
+2、从左到右遍历nums2数组，获取每个元素的下一个更大元素
+  1）栈不为空 且 当前元素大于栈顶元素，则栈顶元素出栈，该栈顶元素的下一个更大元素就是当前元素，记录到map中，循环处理，直到当前元素小于栈顶元素
+  2）当前元素入栈
+3、遍历nums1数组，直接从map中获取当前元素的下一个更大元素，存入结果数组，返回结果
+ */
+class Solution {
+    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
+        Map<Integer, Integer> map = new HashMap<>();
+        Deque<Integer> stack = new ArrayDeque<>();
+        for (int i = 0; i < nums2.length; i++) {
+            while (!stack.isEmpty() && nums2[i] > stack.peek()) {
+                map.put(stack.pop(), nums2[i]);
+            }
+            stack.push(nums2[i]);
+        }
+        int n = nums1.length;
+        int[] res = new int[n];
+        for (int i = 0; i < n; i++) {
+            res[i] = map.getOrDefault(nums1[i], -1);
+        }
+        return res;
+    }
 }
diff --git a/leetcode_Java/Solution0503.java b/leetcode_Java/Solution0503.java
@@ -0,0 +1,26 @@
+// 503. 下一个更大元素 II
+
+
+/*
+单调递减栈：
+1、栈存放的是索引，因为需要索引映射到结果数组
+2、由于是循环数组，故将两个数组拼接在一起模拟循环效果，相当于遍历两次数组，下标通过取余映射到数组索引
+3、从左到右遍历数组，获取每个元素的下一个更大元素
+  1）栈不为空 且 当前元素大于栈顶元素，则栈顶元素出栈，该栈顶元素的下一个更大元素就是当前元素，记录到结果数组中，循环处理，直到当前元素小于栈顶元素
+  2）当前元素入栈
+ */
+class Solution {
+    public int[] nextGreaterElements(int[] nums) {
+        Deque<Integer> stack = new ArrayDeque<>();
+        int n = nums.length;
+        int[] res = new int[n];
+        Arrays.fill(res, -1);
+        for (int i = 0; i < 2 * n; i++) {
+            while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
+                res[stack.pop()] = nums[i % n];
+            }
+            stack.push(i % n);
+        }
+        return res;
+    }
+}
