Java怎么运用单调栈

这篇文章主要介绍“Java怎么运用单调栈”，在日常操作中，相信很多人在Java怎么运用单调栈问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java怎么运用单调栈”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

1.下一个更大元素

题目描述

思路详解

这一题就选取比较暴力 的解法了。

我们先初始化一个与nums等长度的res数组用来存储结果，我们遍历取出nums中的值，到nums2中寻找，直到找到nums2[j] == nums[i] ,我们再从 nums2的 j 之后遍历找到比nums[i]大的数组返回，找不到就返回-1.

代码与结果

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }
}

2.每日温度

题目描述

思路详解

这一题也是使用比较暴力的方法。同上一题一样。

两重循环，显然这种方法时间复杂度较高。这里也提供一种时间复杂度较低的方法。

单调栈

我们维护的是一个差距数组也就是结果数组，首先创建一个栈，判断栈是否为空，若为空直接入栈，若不为空则比较栈顶元素与当前元素，如果当前元素大于当前元素就把差值放入到对应结果数组同时栈顶元素出栈，若当前元素小于结果数组则入栈。

这里给一个动画链接很好董，动画学单调栈。

代码与结果

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        for(int i = 0 ; i < temperatures.length ; i++){
            int res = 0;
            for(int j = i+1 ; j < temperatures.length; j++){
                res++;
                if(temperatures[j] > temperatures[i]){
                    answer[i] = res;
                    break;
                } 
            }
        }
        return answer;
    }
}

3.下一个更大元素II

题目描述

思路详解

本题的思路呢单调栈，问题一暴力破解，这个题要使用单调栈了。

原理同第二题的方法一样，就在循环上注意一下就可以了。直接上代码，不董的可以看第二题的视频再来看这个哦。

代码与结果

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n * 2 - 1; i++) {//最多循环一次，只需要2*n-1就够用了
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ret[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);//利用取模来进行循环也是一种常用的方法
        }
        return ret;
    }
}

到此，关于“Java怎么运用单调栈”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！