題目

給定一個不含重復(fù)值的數(shù)組arr，找到一個i位置左邊和右邊離i位置最近且值比arr[i]小的位置歼冰。返回所有位置的相應(yīng)信息。
arr = [3,4,1,5,6,2,7]
返回如下二維數(shù)組作為結(jié)果
{
?{-1, 2},
?{ 0, 2},
?{-1,-1},
?{ 2, 5},
?{ 3, 5},
?{ 2,-1},
?{ 5,-1}
}
-1表示不存在。所以上面的結(jié)果表示在arr中抵代，0位置左邊和右邊離0位置最近且值比arr[0]小的位置是-1或2；1位置左邊和右邊離1最近且值比arr[1]小的值是0和2建瘫；2位置左邊和右邊比2最近且值比arr[2]小的是-1和-1……
進階問題：給定一個可能含有重復(fù)的數(shù)組arr崭捍，找到一個 i 位置左邊和右邊離 i 最近且值比arr[i]小的位置。返回所有位置的相應(yīng)信息啰脚。

要求

如果arr的長度為N殷蛇，實現(xiàn)原問題和進階問題的解法，時間復(fù)雜度都達到O(N)

思路

? ?關(guān)鍵在于生成所有的位置相應(yīng)信息橄浓，時間復(fù)雜度做到O(N)粒梦，這需要使用到單調(diào)棧結(jié)構(gòu)。
? ?原問題：準備一個棧荸实，記為stack<Integer> ,棧中放入的元素是數(shù)組的位置匀们，開始時stack為空，如果找到每一個 i 位置左邊和右邊離 i 位置最近且值比arr[i]小的位置准给，那么需要讓stack從棧頂?shù)綏５椎奈恢盟写淼闹凳菄栏襁f減昼蛀；找到每一個位置 i 位置的左邊和者右邊離 i 最近且值比arr[i]大的位置，那么需要讓stack從棧頂?shù)綏５椎奈恢盟淼闹凳菄栏裨龅摹?br> ? ?下面用例子來展示單調(diào)棧的使用和求解流程圆存，初始時arr={3,4,1,5,6,7},stack從棧頂?shù)綏５诪?{}
? ?遍歷到arr[0]==3,發(fā)現(xiàn)stack為空叼旋，就直接放入0位置。stack從棧頂?shù)綏５诪椋簕0位置（值為3）}沦辙；
? ?遍歷到arr][1]==4,發(fā)現(xiàn)直接放入1位置不會破壞stack從棧頂?shù)綏５椎奈恢盟淼闹凳菄栏襁f減的夫植，那么就是直接放入。stack從棧頂?shù)綏５滓淮螢椋簕1位置(值是4)油讯、0位置(值是3)}详民；
? ?遍歷到arr[2]==1,發(fā)現(xiàn)直接放入2位置(值是1)，會破壞stack從棧頂?shù)綏５椎奈恢弥凳菄栏襁f減的陌兑，所以從stack開始彈出位置沈跨。如果 x 位置被彈出，在棧中位于x的位置下面的位置兔综，就是x位置左邊離x位置最近且值比arr[x]小的位置饿凛；當前遍歷的位置就是 x 位置右邊離 x 位置最近且值arr[x]小的位置。從stack中彈出位置1之后软驰，在棧中位于1位置下面位置0涧窒，當前遍歷的位置是2，所以ans[1]={0,2}。彈出1位置之后，發(fā)現(xiàn)放入2位置(值是1)還會破壞stack從棧頂?shù)綏５椎奈恢弥凳菄栏襁f減的歪赢，所以繼續(xù)彈出位置0酷勺。在0位置下面已經(jīng)沒有位置戴已，說明位置0左邊不存在比arr[0]小的值固该，當前遍歷到的位置2，所以ans={1,2}糖儡，stack已經(jīng)為空伐坏，所以被放入的2位置(值是1)，stack從棧頂?shù)綏５诪椋簕2位置（值是1）};
? ?遍歷到arr[3]==5休玩，發(fā)現(xiàn)直接放入3位置著淆，不會破壞 stack從棧頂?shù)綏５椎奈恢盟淼闹凳菄栏襁f減的劫狠，那么直接放入拴疤。stack從棧頂?shù)綏ｍ斠来螢?{3位置(值是5)、2位置(值是1)};
? ?遍歷到arr[4]==6独泞，發(fā)現(xiàn)直接放入4位置呐矾，不會破壞stack從棧頂?shù)綏５椎奈恢盟淼闹凳菄栏襁f減的，那么直接放入懦砂。 stack從頂?shù)嚼獾滓来螢?{4位置(值是6)蜒犯、3位置(值是5)、2位置(值是1)}荞膘；
? ?遍歷到arr[5]==2罚随，發(fā)現(xiàn)直接放入5位置，會破壞stack從棧頂?shù)綏５椎奈恢盟淼闹凳菄栏襁f減的羽资，所以開始彈出位置淘菩，彈出位置4，棧中它的下面是位置3屠升，當前是位置5潮改，ans[4]={3,5}。彈出位置3腹暖，棧中它的下面是位置2汇在，當前是位5，ans[3]＝{2,5}脏答。然后放入5位置就不會破壞stack的單調(diào)性了糕殉。stack從從棧頂?shù)綏５滓来螢?{5位置(值是2)、2位置(值是1)}殖告；
? ?遍歷到arr[6]＝7糙麦，發(fā)現(xiàn)直接放入6位置，不會破壞tack從棧頂?shù)綏５偷奈恢盟淼闹凳菄栏襁f減的丛肮，那么直接放入赡磅，stack從找棧頂棧底依次為:{6位置(值是7)、5位置(值是2)宝与、2位置(值是1)｝;
遍歷階段結(jié)束后焚廊，清算中剩下的位置冶匹。
? ?彈出6位置，棧中它的下面是位置5咆瘟，6位置是清算階段彈出的嚼隘，所以ans[6]＝{5，1};
? ?彈出5位置袒餐，棧中它的下面是位置2飞蛹，5位置是清算階段彈出的，所以ans[5]＝{2灸眼，-1}卧檐；
? ?彈出2位置，棧它的下面沒有位置了焰宣，2位置是清算階段彈出的霉囚，所以ans[2]={-1，-1}匕积；
? ?至此盈罐，已經(jīng)全部生成了每個位置的信息。全過程查看getNearLessNoRepear()方法

? ?下面證明在單調(diào)棧中闪唆，如果 x 位置被彈出盅粪，在棧中位于 x 位置下面的位置為什么就是 x 位置左邊離 x 位置最近且值比arr[x]小的位置；當前遍歷到的位置就是 x 位置右邊離 x 位置最近且值比arr[x]小的位置悄蕾。假設(shè) stack當前棧頂位置是x票顾，值是5；x下面是 i 位置笼吟，值是1库物；當前遍歷到 j 位置，值是4.如圖下圖所示贷帮，請注意整個數(shù)組中是沒有重復(fù)值的戚揭。

示意圖

? ?當前來到 j 位置，但是 x 位置已經(jīng)在棧中撵枢，所以 x 位置肯定在 j 位置的左邊：……5 (x 位置)……4( j 位置)……民晒。如果在5和4之間存在小于5的數(shù)，那么沒等遍歷到當前的4锄禽，x 位置(值是5)就已經(jīng)被彈出了潜必，輪不到當前位置的4來讓 x 位置的5彈出，所以5和4之間的數(shù)要么沒有沃但，要么一定比5大磁滚，所以 x 位置右邊離 x 位置最近且小于arr[x]的位置就是 j 位置。
? ?當前彈出的是 x 位置，x 位置下面的是位置 i 垂攘。i 比 x 早進棧维雇，所以 i 位置肯定在 x 位置的左邊：……1( i 位置)……5( x 位置)……。如果在1和5之間存在小于1的數(shù)晒他，那么位置 (值是1) 會被提前彈出吱型，在棧中 i 位置和 x 位置就不可能貼在一起。如果在1和5之間存在大于1但小于5的數(shù)陨仅，那么在棧中 i 位置和 x 位置之間一定會夾上一個別的位置津滞，也不可能貼在一起，所以1和5之同的數(shù)要么沒有灼伤，要么一定比5大触徐，那么 x 位置左邊離 x 位置最近且小于arr[x] 的位置就是 i 位置
? ? 證明完畢。

進階問題饺蔑，可能含有重復(fù)值的數(shù)組如何使用單調(diào)棧锌介。
? ? 其實整個過程和原問題的解法差不多嗜诀，舉個例子來說明猾警，初始時arr={3,1,3,4,3,5,3,2,2}， stack從棧頂?shù)綏５诪椋簕}
? ?遍歷到arr[0]==3隆敢，發(fā)現(xiàn)stack為空发皿，就直接放入0位置，stak從棧頂?shù)綏５诪?{0位置(值是3)};
? ?遍歷到arr[1]==1拂蝎，從中彈出位置0穴墅，并且得到ans[0]={-1,1}，位置1進棧温自， stack從棧頂?shù)綏５诪椋簕1位置(值是1)｝玄货；
? ?遍歷到arr[2]==3，發(fā)現(xiàn)位置2可以直接放入悼泌，stack從棧頂?shù)綏５滓来螢椋簕2位置(值是3)松捉、1位置(值是1)};
? ?遍歷到arr[3]==4，發(fā)現(xiàn)位置3可以直接放入馆里。stack從棧頂?shù)綏５滓来螢椋簕3位置(值是4)隘世、2位置(值是3)、1位置(值是1)};
? ?遍歷到arr[4]==3鸠踪，從棧中彈出位置3丙者，并且得到ans[3]＝{2,4}。此時發(fā)現(xiàn)棧頂是位置2营密，值是3械媒；當前歷到位置4，值也是3评汰，所以兩個位置壓在一起纷捞。stack從棧頂?shù)綏５滓来螢椋簕[2位置侣集，4位置] (值是3)、1位置(值是1)};
? ?遍歷到arr[5]==5兰绣，發(fā)現(xiàn)位置5可以直接放入世分， stack從棧頂?shù)綏５滓来螢?{5位置(值是5)、[2位置缀辩，4位置] (值是3)臭埋、1位置(值是1)}；
? ?遍歷到arr[6]==3臀玄，從棧中彈出位置5瓢阴，在棧中位置5的下面是[2位置，4位置]健无，選最晚加入的4位置荣恐，當前遍歷到位置6，所以得到ans[5]＝{4累贤，6}叠穆。位置6進棧，發(fā)現(xiàn)又是和頂位置代表的值相等的情況臼膏，所以繼續(xù)壓在一起硼被， stack從棧頂?shù)降滓来螢?{[2位置，4位置渗磅，6位置] (值是3)嚷硫、1位置(值是1)};
? ?遍歷到arr[7]==2，從棧中彈出[2位置始鱼，4位置仔掸，6位置]，在棧中這些位置下面的是1位置医清，當前是7位置起暮，所以得到ans[2]={1,7}，ans[3]={1,7}状勤，ans[4]={1,7}鞋怀。位置7進棧， stack從棧頂?shù)綏５滓来螢椋簕7位置(值是2)持搜、1位置(值是1)};
? ?遍歷到arr[8]==2密似，發(fā)現(xiàn)位置8可以直接進，并且又是相等的情況葫盼，stack從棧頂?shù)綏５滓来螢椋簕[7位置残腌，8位置] (值是2)、1位置(值是1)}。
? ?遍歷完成后抛猫，開始清算階段:
? ?彈出[7位置蟆盹，8位置]，生成ans[7]={1,-1}闺金，ans[8]={1,-1};
? ?彈出1位置逾滥，生成ans[1]＝{-1,-1}；
? ?全過程查看getNearLess()方法

代碼演示

package com.itz.zcy.stackAndQueue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 給定一個不含重復(fù)值的數(shù)組arr败匹，找到一個i位置左邊和右邊離i位置最近且值比arr[i]小的位置寨昙。返回所有位置的相應(yīng)信息。
 * arr = [3,4,1,5,6,2,7]
 * 返回如下二維數(shù)組作為結(jié)果
 * {
 * {-1, 2},
 * { 0, 2},
 * {-1,-1},
 * { 2, 5},
 * { 3, 5},
 * { 2,-1},
 * { 5,-1}
 * }
 * -1表示不存在掀亩。所以上面的結(jié)果表示在arr中舔哪，0位置左邊和右邊離0位置最近且值比arr[0]小的位置是-1或2；
 * 1位置左邊和右邊離1最近且值比arr[1]小的值是0和2槽棍；2位置左邊和右邊比2最近且值比arr[2]小的是-1和-1……
 * <p>
 * 進階問題：給定一個可能含有重復(fù)的數(shù)組arr捉蚤，找到一個 i 位置左邊和右邊離 i 最近且值比arr[i]小的位置。返回所有位置的相應(yīng)信息炼七。
 */
public class MonotonousStack {

    /**
     * 采用的是原始的暴力解法缆巧，該方法的時間復(fù)雜度是O(N^2)
     *
     * @param arr 需要操作的數(shù)組
     * @return
     */
    public static int[][] rightWay(int[] arr) {
        int[][] res = new int[arr.length][2];
        for (int i = 0; i < arr.length; i++) {
            int leftLessIndex = -1;
            int rightLessIndex = -1;
            int cur = i - 1;
//            向i位置左邊尋找最近最小的
            while (cur >= 0) {
                if (arr[cur] < arr[i]) {
                    leftLessIndex = cur;
                    break;
                }
                cur--;
            }
            cur = i + 1;
//            向i位置右邊尋找最近最小的
            while (cur < arr.length) {
                if (arr[cur] < arr[i]) {
                    rightLessIndex = cur;
                    break;
                }
                cur++;
            }
            res[i][0] = leftLessIndex;
            res[i][1] = rightLessIndex;
        }
        return res;
    }

    /**
     * 針對的是原始數(shù)組沒有重復(fù)值的情況
     * 向遍歷數(shù)組。在整個中特石，每個位置都進棧一次盅蝗，出棧一次鳖链，所以這個流程的時間復(fù)雜度即使O(N)姆蘸。對數(shù)組的遍歷也是只有一次
     * 在這個過程中分為兩個階段，在這個遍歷階段對數(shù)組進行遍歷芙委，然后把能找的的都存入數(shù)組中把右邊能找都左邊找不到也存入了逞敷，
     * 清算階段把，把左邊能找到灌侣，右邊找不到的和最小的存入推捐。
     * @param arr 需要操作的數(shù)組
     * @return
     */
    public static int[][] getNearLessNoRepeat(int[] arr) {
        int[][] res = new int[arr.length][2];
        // 定義一個臨時棧
        Stack<Integer> stack = new Stack<>();
//        遍歷階段
        for (int i = 0; i < arr.length; i++) {
//            判斷但放入的時候后 stack從棧頂?shù)綏５撞皇菃握{(diào)遞減的
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                int popIndex = stack.pop();
//                當棧為空的時候 表示下面沒有了是-1
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
                res[popIndex][0] = leftLessIndex;
                res[popIndex][1] = i;
            }
            stack.push(i);
        }
//      清算那些找不到的情況
        while (!stack.isEmpty()) {
            int popIndex = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = -1;
        }
        return res;
    }

    /**
     * 進階問題：在arr數(shù)組中存在重復(fù)的元素
     * 方法和沒有重復(fù)的差不多，只是用List來做節(jié)點存入stack中侧啼，多引入一種數(shù)據(jù)結(jié)構(gòu)
     * 在遇見重復(fù)的選最晚的加入
     * @param arr
     * @return
     */
    public static int[][] getNearLess(int[] arr){
        int[][] res = new int[arr.length][2];
        Stack<List<Integer>> stack = new Stack<>();
//        遍歷階段
        for (int i =0;i<arr.length;i++){
            while (!stack.isEmpty()&&arr[stack.peek().get(0)]>arr[i]){
                List<Integer> popIs = stack.pop();
//                取位于下面位置中牛柒，加入最晚的
                int leftLessIndex = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
                for (Integer popi:popIs){
                    res[popi][0] = leftLessIndex;
                    res[popi][1] = i;
                }
            }
            if (!stack.isEmpty()&&arr[stack.peek().get(0)]==arr[i]){
                stack.peek().add(Integer.valueOf(i));
            }else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                stack.add(list);
            }
        }
//        清算階段
        while (!stack.isEmpty()) {
            List<Integer> popIs = stack.pop();
//            取位于下面位置中，加入最晚的
            int leftLessIndex = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
            for (Integer popi:popIs){
                res[popi][0] = leftLessIndex;
                res[popi][1] = -1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 1, 5, 6, 2, 7};
        int[] a = {3,1,3,4,3,5,3,2,2};
        System.out.println(Arrays.deepToString(getNearLessNoRepeat(arr)));
        System.out.println(Arrays.deepToString(rightWay(arr)));
        System.out.println(Arrays.deepToString(getNearLess(arr)));
        System.out.println(Arrays.deepToString(getNearLess(a)));

//        [[-1, 2], [0, 2], [-1, -1], [2, 5], [3, 5], [2, -1], [5, -1]]
//        [[-1, 2], [0, 2], [-1, -1], [2, 5], [3, 5], [2, -1], [5, -1]]
//        [[-1, 2], [0, 2], [-1, -1], [2, 5], [3, 5], [2, -1], [5, -1]]
//        [[-1, 1], [-1, -1], [1, 7], [2, 4], [1, 7], [4, 6], [1, 7], [1, -1], [1, -1]]
    }
}

總結(jié)

在方法一用最原始的方法使用暴力的方法對時間復(fù)雜度是O(N^2)痊乾，在方法二中使用了單調(diào)棧的數(shù)據(jù)結(jié)構(gòu)皮壁，arr數(shù)組和進棧出棧都只做了一次所以時間復(fù)雜度是O(N)。進階問題大致的思路和其他差不多哪审，就是多引入了一種數(shù)據(jù)結(jié)構(gòu)蛾魄，引入了Lis來存儲元素，對于重復(fù)的元素就解決了，但是他們的時間復(fù)雜度還是O(N)

文獻：左程云著 《程序員代碼面試指南IT名企算法與數(shù)據(jù)結(jié)構(gòu)題目最優(yōu)解》（第二版）
版權(quán)聲明：此文版權(quán)歸作者所有滴须！