496. Next Greater Element I
https://leetcode.com/problems/next-greater-element-i/
单调栈问题,参考:https://leetcode.com/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
https://leetcode.com/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; // 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/
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;
}
}