这是我在Leetcode中做过的一个题——验证回文字符串 Ⅱ,我把它分享给你们:
这是原题链接:https://leetcode-cn.com/problems/valid-palindrome-ii/
如果感觉我做的还行的话,记得点赞。
思路分析:
通过Stack、HashMap解决
- 先遍历大数组nums2,首先将第一个元素入栈;
- 继续遍历,当当前元素小于栈顶元素时,继续将它入栈;当当前元素大于栈顶元素时,栈顶元素出栈,此时应将该出栈的元素与当前元素形成key-value键值对,存入HashMap中;
- 当遍历完nums2后,得到nums2中元素所对应的下一个更大元素的hash表;
- 遍历nums1的元素在hashMap中去查找‘下一个更大元素’,当找不到时则为-1。
代码:
public class Solution {
public int[] nextGreaterElement(int[] findNums, int[] nums) {
Stack < Integer > stack = new Stack < > ();
HashMap < Integer, Integer > map = new HashMap < > ();
int[] res = new int[findNums.length];
for (int i = 0; i < nums.length; i++) {
while (!stack.empty() && nums[i] > stack.peek())
map.put(stack.pop(), nums[i]);
stack.push(nums[i]);
}
while (!stack.empty())
map.put(stack.pop(), -1);
for (int i = 0; i < findNums.length; i++) {
res[i] = map.get(findNums[i]);
}
return res;
}
}