Java每日一题:496. 下一个更大元素 I

这是我在Leetcode中做过的一个题——验证回文字符串 Ⅱ,我把它分享给你们:

这是原题链接:https://leetcode-cn.com/problems/valid-palindrome-ii/

如果感觉我做的还行的话,记得点赞。

Java每日一题:496. 下一个更大元素 I

Java每日一题:496. 下一个更大元素 IJava每日一题:496. 下一个更大元素 I

思路分析:

通过Stack、HashMap解决

  1. 先遍历大数组nums2,首先将第一个元素入栈;
  2. 继续遍历,当当前元素小于栈顶元素时,继续将它入栈;当当前元素大于栈顶元素时,栈顶元素出栈,此时应将该出栈的元素与当前元素形成key-value键值对,存入HashMap中;
  3. 当遍历完nums2后,得到nums2中元素所对应的下一个更大元素的hash表;
  4. 遍历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;
    }
}

 

 

上一篇:力扣496题(单调栈)


下一篇:【LeetCode-496】下一个更大元素 I