[TOC]

9. 用兩個棧實現(xiàn)隊列

用兩個棧來實現(xiàn)一個隊列，完成隊列的 Push 和 Pop 操作半抱。

mysolution

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if (stack2.isEmpty()) {
            tranferStack1ToStack2();
        }
        return stack2.pop();
    }
    
    private void tranferStack1ToStack2() {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
}

解題思路

in 棧用來處理入棧（push）操作，out 棧用來處理出棧（pop）操作膜宋。一個元素進(jìn)入 in 棧之后窿侈，出棧的順序被反轉(zhuǎn)。當(dāng)元素要出棧時秋茫，需要先進(jìn)入 out 棧史简，此時元素出棧順序再一次被反轉(zhuǎn)，因此出棧順序就和最開始入棧順序是相同的肛著，先進(jìn)入的元素先退出圆兵，這就是隊列的順序。

[圖片上傳失敗...(image-dc5b93-1633656573051)]

包含 min 函數(shù)的棧

實現(xiàn)一個包含 min() 函數(shù)的棧枢贿，該方法返回當(dāng)前棧中最小的值殉农。

mysolution

import java.util.Stack;

public class Solution {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    
    public void push(int node) {
        stack1.push(node);
        if (stack2.isEmpty()) {
            stack2.push(node);
        } else if (node < stack2.peek()) {
            stack2.push(node);
        } else {
            stack2.push(stack2.peek());
        }
            
    }
    
    public void pop() {
        stack1.pop();
        stack2.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }
}

解題思路

使用一個額外的 minStack，棧頂元素為當(dāng)前棧中最小的值萨咕。在對棧進(jìn)行 push 入棧和 pop 出棧操作時统抬，同樣需要對 minStack 進(jìn)行入棧出棧操作，從而使 minStack 棧頂元素一直為當(dāng)前棧中最小的值危队。在進(jìn)行 push 操作時，需要比較入棧元素和當(dāng)前棧中最小值钙畔，將值較小的元素 push 到 minStack 中茫陆。

[圖片上傳失敗...(image-b6f180-1633656573051)]

private Stack<Integer> dataStack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();

public void push(int node) {
    dataStack.push(node);
    minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node));
}

public void pop() {
    dataStack.pop();
    minStack.pop();
}

public int top() {
    return dataStack.peek();
}

public int min() {
    return minStack.peek();
}

棧的壓入、彈出序列

輸入兩個整數(shù)序列擎析，第一個序列表示棧的壓入順序簿盅，請判斷第二個序列是否為該棧的彈出順序挥下。假設(shè)壓入棧的所有數(shù)字均不相等。

例如序列 1,2,3,4,5 是某棧的壓入順序桨醋，序列 4,5,3,2,1 是該壓棧序列對應(yīng)的一個彈出序列棚瘟，但 4,3,5,1,2 就不可能是該壓棧序列的彈出序列。

mysolution

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int pushIndex = 0;
        int popIndex = 0;
        while (pushIndex < pushA.length && popIndex < pushA.length) {
            if (pushA[pushIndex] == popA[popIndex]) {
                pushIndex++;
                popIndex++;
                continue;
            }
            if (!stack.isEmpty() && popA[popIndex] == stack.peek()) {
                stack.pop();
                popIndex++;
                continue;
            }
            stack.push(pushA[pushIndex++]);
           
        }
        if (pushIndex == pushA.length && popIndex < popA.length) {
            while (popIndex < popA.length) {
                if (popA[popIndex] != stack.peek()) {
                    return false;
                }
                stack.pop();
                popIndex++;
            }
        }
        return true;
    }      
}

解題思路

使用一個棧來模擬壓入彈出操作喜最。每次入棧一個元素后偎蘸，都要判斷一下棧頂元素是不是當(dāng)前出棧序列 popSequence 的第一個元素，如果是的話則執(zhí)行出棧操作并將 popSequence 往后移一位瞬内，繼續(xù)進(jìn)行判斷迷雪。

public boolean IsPopOrder(int[] pushSequence, int[] popSequence) {
    int n = pushSequence.length;
    Stack<Integer> stack = new Stack<>();
    for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {
        stack.push(pushSequence[pushIndex]);
        while (popIndex < n && !stack.isEmpty() 
                && stack.peek() == popSequence[popIndex]) {
            stack.pop();
            popIndex++;
        }
    }
    return stack.isEmpty();
}

40. 最小的 K 個數(shù)

Mysolution

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        if (k <= 0) {
            return result;
        }
        buildHeap(input);
        for(int i = 0; i < k; i++) {
            int tmp = input[0];
            input[0] = input[input.length - i - 1];
            input[input.length - i - 1] = tmp;
            result.add(tmp);
          
            adjustHeap(input, 0, input.length - i - 2);
        }
        return result;
    }
    
    private void buildHeap(int[] input) {
        int start = (input.length - 2) / 2;
        for (int i = start; i >= 0; i--) {
            adjustHeap(input, i, input.length - 1);
        }
    }
    
    private void adjustHeap(int[] input, int position, int end) {
        int subPosition = position * 2 + 1;
        int tmp = input[position];
        while (subPosition <= end) {
            if (subPosition + 1 <= end && input[subPosition + 1] < input[subPosition]) {
                subPosition += 1;
            }
            if (tmp < input[subPosition]) {
                break;
            }
            input[position] = input[subPosition];
            position = subPosition;
            subPosition = position * 2 + 1;
        }
        input[position] = tmp;
    }
}

解題思路

大小為 K 的最小堆
復(fù)雜度：O(NlogK) + O(K)
特別適合處理海量數(shù)據(jù)
維護(hù)一個大小為 K 的最小堆過程如下：使用大頂堆。在添加一個元素之后虫蝶，如果大頂堆的大小大于 K章咧，那么將大頂堆的堆頂元素去除，也就是將當(dāng)前堆中值最大的元素去除能真，從而使得留在堆中的元素都比被去除的元素來得小赁严。

應(yīng)該使用大頂堆來維護(hù)最小堆，而不能直接創(chuàng)建一個小頂堆并設(shè)置一個大小粉铐，企圖讓小頂堆中的元素都是最小元素误澳。

Java 的 PriorityQueue 實現(xiàn)了堆的能力，PriorityQueue 默認(rèn)是小頂堆秦躯，可以在在初始化時使用 Lambda 表達(dá)式 (o1, o2) -> o2 - o1 來實現(xiàn)大頂堆忆谓。其它語言也有類似的堆數(shù)據(jù)結(jié)構(gòu)。

public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
    if (k > nums.length || k <= 0)
        return new ArrayList<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    for (int num : nums) {
        maxHeap.add(num);
        if (maxHeap.size() > k)
            maxHeap.poll();
    }
    return new ArrayList<>(maxHeap);
}

快速選擇

復(fù)雜度：O(N) + O(1)
只有當(dāng)允許修改數(shù)組元素時才可以使用
快速排序的 partition() 方法踱承，會返回一個整數(shù) j 使得 a[l..j-1] 小于等于 a[j]倡缠，且 a[j+1..h] 大于等于 a[j]，此時 a[j] 就是數(shù)組的第 j 大元素茎活￡悸伲可以利用這個特性找出數(shù)組的第 K 個元素，這種找第 K 個元素的算法稱為快速選擇算法载荔。

public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
    ArrayList<Integer> ret = new ArrayList<>();
    if (k > nums.length || k <= 0)
        return ret;
    findKthSmallest(nums, k - 1);
    /* findKthSmallest 會改變數(shù)組盾饮，使得前 k 個數(shù)都是最小的 k 個數(shù) */
    for (int i = 0; i < k; i++)
        ret.add(nums[i]);
    return ret;
}

public void findKthSmallest(int[] nums, int k) {
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int j = partition(nums, l, h);
        if (j == k)
            break;
        if (j > k)
            h = j - 1;
        else
            l = j + 1;
    }
}

private int partition(int[] nums, int l, int h) {
    int p = nums[l];     /* 切分元素 */
    int i = l, j = h + 1;
    while (true) {
        while (i != h && nums[++i] < p) ;
        while (j != l && nums[--j] > p) ;
        if (i >= j)
            break;
        swap(nums, i, j);
    }
    swap(nums, l, j);
    return j;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

41.1 數(shù)據(jù)流中的中位數(shù)

如何得到一個數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值懒熙，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值丘损。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值工扎。

/* 大頂堆徘钥，存儲左半邊元素 */
private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
/* 小頂堆，存儲右半邊元素肢娘，并且右半邊元素都大于左半邊 */
private PriorityQueue<Integer> right = new PriorityQueue<>();
/* 當(dāng)前數(shù)據(jù)流讀入的元素個數(shù) */
private int N = 0;

public void Insert(Integer val) {
    /* 插入要保證兩個堆存于平衡狀態(tài) */
    if (N % 2 == 0) {
        /* N 為偶數(shù)的情況下插入到右半邊呈础。
         * 因為右半邊元素都要大于左半邊舆驶，但是新插入的元素不一定比左半邊元素來的大，
         * 因此需要先將元素插入左半邊而钞，然后利用左半邊為大頂堆的特點沙廉，取出堆頂元素即為最大元素，此時插入右半邊 */
        left.add(val);
        right.add(left.poll());
    } else {
        right.add(val);
        left.add(right.poll());
    }
    N++;
}

public Double GetMedian() {
    if (N % 2 == 0)
        return (left.peek() + right.peek()) / 2.0;
    else
        return (double) right.peek();
}

字符流中第一個不重復(fù)的字符

思路

字符出現(xiàn)次數(shù)的判斷（不重復(fù)字符）：
這個做法大致相同臼节，利用 Hash 思想采用128大小的計數(shù)數(shù)組進(jìn)行計數(shù)也好撬陵，或者是使用 Map 鍵值對映射也好，都差不多官疲，使用數(shù)組會更簡單袱结。

字符出現(xiàn)順序的判斷（第一個字符）：
這里就是改進(jìn)的關(guān)鍵之處了，容易發(fā)現(xiàn)途凫，字符流中不重復(fù)的字符可能同時存在多個垢夹，我們只要把這些 “不重復(fù)字符” 保存起來就可以，而無需保存那些重復(fù)出現(xiàn)的字符维费，而為了維護(hù)字符出現(xiàn)的順序果元，我們使用隊列（先進(jìn)先出）這一結(jié)構(gòu)，先出現(xiàn)的不重復(fù)字符先輸出：

入隊：獲取字符流中的一個字符時犀盟，當(dāng)我們判斷它是不重復(fù)時而晒，將它加入隊列；
輸出/出隊：注意阅畴，因為隊列中存儲的 “不重復(fù)字符” 在一系列的流讀取操作后倡怎，隨時有可能改變狀態(tài)（變重復(fù)），所以贱枣，隊列中的字符不能直接輸出监署，要先進(jìn)行一次重復(fù)判斷，如果發(fā)現(xiàn)隊頭字符已經(jīng)重復(fù)了纽哥，就將它移出隊列并判斷新的隊頭钠乏，否則，輸出隊頭的值春塌；
復(fù)雜度計算：
從上面的描述來看晓避，好像存在一個循環(huán)，隊列的長度好像無邊無際只壳，就給人一種O(n)的感覺俏拱，其實，并不是吕世，有如下結(jié)論：

通過分析可以發(fā)現(xiàn)彰触，循環(huán)（出隊）的最大次數(shù)其實就是隊列的長度，而隊列的長度最大為128命辖；
并且隨著時間的推移况毅，隊列長度 總體 先增大，后減小尔艇，正常條件下尔许，最終隊列會為空（因為隨著字符流的增大，重復(fù)的字符會越來越多终娃，隊列就會不斷地移除元素而越來越短）味廊；
更愉快的是，如果隊列長度不減小棠耕，則循環(huán)就只執(zhí)行一次余佛，返回速度快，如果隊列長度減小了窍荧，那么辉巡，循環(huán)次數(shù)上限也就減小了；
所以時間蕊退、空間復(fù)雜度是一致的郊楣，都是常數(shù)級，可是這是為什么呢瓤荔，分析如下：

字符的重復(fù)判斷净蚤，因為使用的是直接 Hash，而且功能是計數(shù)输硝，沒有沖突今瀑，所以是O(1)；
只有不重復(fù)的字符才入隊列点把，但是不重復(fù)的字符有幾個呢橘荠？ASCII字符最多也就128個，那么同一字符會不會多次入隊呢愉粤？ 不會的砾医，見3；
只有隊頭元素變得重復(fù)了才執(zhí)行循環(huán)衣厘，所以執(zhí)行循環(huán)就意味著隊列長度要變小如蚜。要注意，根據(jù)題意影暴，字符的出現(xiàn)次數(shù)只增不減４戆睢！型宙！所以撬呢，出隊的字符不會再入隊，隊列長度總體上只會越來越凶倍摇（或者上升到峰值就不再上升了魂拦，128種字符用盡）毛仪。

import java.util.Queue;
import java.util.LinkedList;
import java.lang.Character;

public class Solution {
    int[] charCnt = new int[128];
    Queue<Character> queue = new LinkedList<Character>();

    //Insert one char from stringstream
    public void Insert(char ch) {
        if (charCnt[ch]++ == 0) //新來的單身字符，入隊
            queue.add(ch);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        Character CHAR = null;
        char c = 0;
        while ((CHAR = queue.peek()) != null) {
            c = CHAR.charValue();
            if (charCnt[c] == 1) //判斷是否脫單了芯勘，沒脫單則輸出
                return c;
            else queue.remove(); //脫單了就移出隊列箱靴，它不會再回來了
        }
        return '#'; //隊空，返回#
    }
}

思路2（其實一樣的）

使用統(tǒng)計數(shù)組來統(tǒng)計每個字符出現(xiàn)的次數(shù)荷愕，本題涉及到的字符為都為 ASCII 碼衡怀，因此使用一個大小為 128 的整型數(shù)組就能完成次數(shù)統(tǒng)計任務(wù)。

使用隊列來存儲到達(dá)的字符安疗，并在每次有新的字符從字符流到達(dá)時移除隊列頭部那些出現(xiàn)次數(shù)不再是一次的元素抛杨。因為隊列是先進(jìn)先出順序，因此隊列頭部的元素為第一次只出現(xiàn)一次的字符荐类。

private int[] cnts = new int[128];
private Queue<Character> queue = new LinkedList<>();

public void Insert(char ch) {
    cnts[ch]++;
    queue.add(ch);
    while (!queue.isEmpty() && cnts[queue.peek()] > 1)
        queue.poll();
}

public char FirstAppearingOnce() {
    return queue.isEmpty() ? '#' : queue.peek();
}

滑動窗口的最大值

給定一個數(shù)組和滑動窗口的大小怖现，找出所有滑動窗口里數(shù)值的最大值。

例如掉冶，如果輸入數(shù)組 {2, 3, 4, 2, 6, 2, 5, 1} 及滑動窗口的大小 3真竖，那么一共存在 6 個滑動窗口，他們的最大值分別為 {4, 4, 6, 6, 6, 5}厌小。

[圖片上傳失敗...(image-84603f-1633656573051)]

解題思路

維護(hù)一個大小為窗口大小的大頂堆恢共，頂堆元素則為當(dāng)前窗口的最大值。

假設(shè)窗口的大小為 M璧亚，數(shù)組的長度為 N讨韭。在窗口向右移動時，需要先在堆中刪除離開窗口的元素癣蟋，并將新到達(dá)的元素添加到堆中透硝，這兩個操作的時間復(fù)雜度都為 log2M，因此算法的時間復(fù)雜度為 O(Nlog2M)疯搅，空間復(fù)雜度為 O(M)濒生。

public ArrayList<Integer> maxInWindows(int[] num, int size) {
    ArrayList<Integer> ret = new ArrayList<>();
    if (size > num.length || size < 1)
        return ret;
    PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);  /* 大頂堆 */
    for (int i = 0; i < size; i++)
        heap.add(num[i]);
    ret.add(heap.peek());
    for (int i = 0, j = i + size; j < num.length; i++, j++) {            /* 維護(hù)一個大小為 size 的大頂堆 */
        heap.remove(num[i]);
        heap.add(num[j]);
        ret.add(heap.peek());
    }
    return ret;
}