leetcode 496, 503, 556. Next Greater Element I, II, III | 496, 503, 556. 下一个更大元素 I,II,III（单调栈）

分手后的思念是犯贱 2022-09-11 07:25 161阅读 0赞

## 496. Next Greater Element I ##

[https://leetcode.com/problems/next-greater-element-i/][https_leetcode.com_problems_next-greater-element-i]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]  
单调栈问题，参考：[https://leetcode.com/problems/next-greater-element-i/discuss/97595/Java-10-lines-linear-time-complexity-O(n)-with-explanation][https_leetcode.com_problems_next-greater-element-i_discuss_97595_Java-10-lines-linear-time-complexity-O_n_-with-explanation]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

class Solution { 
        public int[] nextGreaterElement(int[] nums1, int[] nums2) { 
            HashMap<Integer, Integer> map = new HashMap<>();
            Stack<Integer> stack = new Stack<>();
            for (int n : nums2) { 
                while (!stack.isEmpty() && stack.peek() < n) { 
                    map.put(stack.pop(), n);
                }
                stack.push(n);
            }
            int[] result = new int[nums1.length];
            for (int i = 0; i < nums1.length; i++) { 
                result[i] = map.getOrDefault(nums1[i], -1);
            }
            return result;
        }
    }

## 503. Next Greater Element II ##

[https://leetcode.com/problems/next-greater-element-ii/][https_leetcode.com_problems_next-greater-element-ii]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 3]

class Solution { 
        public int[] nextGreaterElements(int[] nums) { 
            int[] result = new int[nums.length];
            Arrays.fill(result, -1);
            Stack<Integer> valueStack = new Stack<>();
            Stack<Integer> indexStack = new Stack<>();
            for (int i = 0; i < nums.length * 2 - 1; i++) { 
                int index = i % nums.length; // circularly
                while (!valueStack.isEmpty() && valueStack.peek() < nums[index]) { 
                    result[indexStack.pop()] = nums[index];
                    valueStack.pop();
                }
                valueStack.push(nums[index]);
                indexStack.push(index);
            }
            return result;
        }
    }

## 556. Next Greater Element III ##

[https://leetcode.com/problems/next-greater-element-iii/][https_leetcode.com_problems_next-greater-element-iii]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 4]

class Solution { 
        public int nextGreaterElement(int n) { 
            int[] nums = new int[String.valueOf(n).length()];
            int j = nums.length - 1;
            while (n != 0) { 
                nums[j--] = n % 10;
                n /= 10;
            }
            // 找到右边最小的大于i的数
            Stack<Integer> valueStack = new Stack<>();
            Stack<Integer> indexStack = new Stack<>();
            int preIndex = -1;
            boolean valid = false;
            for (int i = nums.length - 1; i >= 0; i--) { 
                while (!valueStack.isEmpty() && valueStack.peek() > nums[i]) { 
                    preIndex = indexStack.pop();
                    valueStack.pop();
                    valid = true;
                }
                valueStack.push(nums[i]);
                indexStack.push(i);
                if (valid) {  // i与i右边最小的大于i的数交换
                    swap(nums, i, preIndex);
                    reverse(nums, i + 1, nums.length - 1); // i右边到结尾的所有数翻转
                    break;
                }
            }
            if (!valid) return -1;
    
            long res = 0;
            for (int num : nums) { 
                res *= 10;
                res += num;
            }
            return res <= Integer.MAX_VALUE ? (int) res : -1;
        }
    
        public void reverse(int[] arr, int i, int j) { 
            for (int k = 0; k < (j - i + 1) / 2; k++) { 
                swap(arr, i + k, j - k);
            }
        }
    
        public void swap(int[] arr, int i, int j) { 
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }

[https_leetcode.com_problems_next-greater-element-i]: https://leetcode.com/problems/next-greater-element-i/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/744a11d25cfe47078ff90515eb90b35f.png
[https_leetcode.com_problems_next-greater-element-i_discuss_97595_Java-10-lines-linear-time-complexity-O_n_-with-explanation]: https://leetcode.com/problems/next-greater-element-i/discuss/97595/Java-10-lines-linear-time-complexity-O%28n%29-with-explanation
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/d9fbead4da4c4353b3c01035b13161ef.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/c47b85dd1f924c63b80a29f580b71aea.png
[https_leetcode.com_problems_next-greater-element-ii]: https://leetcode.com/problems/next-greater-element-ii/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/be161ab4420347dc9a8bed36cd14f533.png
[https_leetcode.com_problems_next-greater-element-iii]: https://leetcode.com/problems/next-greater-element-iii/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/9be6ff47236c417ea83f55ad5da50266.png