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

496. Next Greater Element I

/problems/next-greater-element-i/

单调栈问题，参考：/problems/next-greater-element-i/discuss/97595/Java-10-lines-linear-time-complexity-O(n)-with-explanation

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

/problems/next-greater-element-ii/

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; // circularlywhile (!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

/problems/next-greater-element-iii/

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;}}