2018-09-24 21:52:38
一、Next Greater Element I
问题描述：
问题求解：
本题只需要将nums2中元素的下一个更大的数通过map保存下来，然后再遍历一遍nums1即可。
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] res = new int[nums1.length];
Map<Integer, Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack<>();
for (int num : nums2) {
while (!stack.isEmpty() && stack.peek() < num) map.put(stack.pop(), num);
stack.push(num);
}
for (int i = 0; i < nums1.length; i++) {
res[i] = map.getOrDefault(nums1[i], -1);
}
return res;
}
二、Next Greater Element II
问题描述：
问题求解：
本题和上一题应该来说是差不多的，都可以使用Stack来对数据进行维护，有两个需要注意的地方，一个是本题中的循环性，解决循环性的方法就是在数组后再加上一个数组即可。
二一个是本题中并没有说是无重复元素的，因此只能在栈中保存index值。
栈中保存的只有第一次遍历的下标值，第二次就没有必要再进行压栈操作了，另外，栈中保存的是递减的数的index。
public int[] nextGreaterElements(int[] nums) {
int[] res = new int[nums.length];
Arrays.fill(res, -1);
Stack<Integer> stack = new Stack<>();
int n = nums.length;
for (int i = 0; i < 2 * n; i++) {
int num = nums[i % n];
while (!stack.isEmpty() && nums[stack.peek()] < num) res[stack.pop()] = num;
if (i < n) stack.push(i);
}
return res;
}
三、Next Greater Element III
问题描述：
问题求解：
就是一条按字典序的下一个Permutation。
public int nextGreaterElement(int n) {
char[] c = String.valueOf(n).toCharArray();
int idx = c.length - 2;
while (idx >= 0 && c[idx] >= c[idx + 1]) idx--;
if (idx == -1) return -1;
int j = c.length - 1;
while (j >= 0 && c[j] <= c[idx]) j--;
swap(c, idx, j);
reverseSort(c, idx + 1, c.length - 1);
long res = Long.valueOf(String.valueOf(c));
return res >= Integer.MAX_VALUE ? -1 : (int)res;
}
private void swap(char[] c, int i, int j) {
char tmp = c[i];
c[i] = c[j];
c[j] = tmp;
}
private void reverseSort(char[] c, int start, int end) {
if (start >= end) return;
while (start < end) {
swap(c, start, end);
start++;
end--;
}
}