Java怎么運用單調(diào)棧

這篇文章主要介紹“Java怎么運用單調(diào)?！?，在日常操作中，相信很多人在Java怎么運用單調(diào)棧問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java怎么運用單調(diào)?！钡囊苫笥兴鶐椭?！接下來，請跟著小編一起來學習吧！

1.下一個更大元素

題目描述

思路詳解

這一題就選取比較暴力 的解法了。

我們先初始化一個與nums等長度的res數(shù)組用來存儲結(jié)果，我們遍歷取出nums中的值，到nums2中尋找，直到找到nums2[j] == nums[i] ,我們再從 nums2的 j 之后遍歷找到比nums[i]大的數(shù)組返回，找不到就返回-1.

代碼與結(jié)果

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.每日溫度

題目描述

思路詳解

這一題也是使用比較暴力的方法。同上一題一樣。

兩重循環(huán)，顯然這種方法時間復雜度較高。這里也提供一種時間復雜度較低的方法。

單調(diào)棧

我們維護的是一個差距數(shù)組也就是結(jié)果數(shù)組，首先創(chuàng)建一個棧，判斷棧是否為空，若為空直接入棧，若不為空則比較棧頂元素與當前元素，如果當前元素大于當前元素就把差值放入到對應結(jié)果數(shù)組同時棧頂元素出棧，若當前元素小于結(jié)果數(shù)組則入棧。

這里給一個動畫鏈接很好董，動畫學單調(diào)棧。

代碼與結(jié)果

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

題目描述

思路詳解

本題的思路呢單調(diào)棧，問題一暴力破解，這個題要使用單調(diào)棧了。

原理同第二題的方法一樣，就在循環(huán)上注意一下就可以了。直接上代碼，不董的可以看第二題的視頻再來看這個哦。

代碼與結(jié)果

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++) {//最多循環(huán)一次，只需要2*n-1就夠用了
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ret[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);//利用取模來進行循環(huán)也是一種常用的方法
        }
        return ret;
    }
}

到此，關于“Java怎么運用單調(diào)?！钡膶W習就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>