[左神面试指南] 栈和队列篇

CD5 设计一个有 getMin 功能的栈

/*
 * 维护一个最小栈minStack
 * dataStack每压入一个数, minStack也压入一个当前状态的最小值
 */
public class CD5_1
{
    public static class Solution
    {
        public Stack<Integer> dataStack = new Stack<>();
        public Stack<Integer> minStack = new Stack<>();

        public void push(int data)
        {
            dataStack.push(data);
            if (minStack.isEmpty()) minStack.push(data);
            else minStack.push(Math.min(minStack.peek(), data));
        }

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

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

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        Scanner in = new Scanner(System.in);
        int N = Integer.parseInt(in.nextLine());
        while (N-- > 0)
        {
            String s = in.nextLine();
            if (s.startsWith("push"))
                solution.push(Integer.parseInt(s.split(" ")[1]));
            else if (s.startsWith("pop"))
                solution.pop();
            else
                System.out.println(solution.getMin());
        }
    }
}

/*
 * 维护一个最小栈minStack
 * dataStack压入一个数data时, 当data<=minStack.peek()时, minStack才压入
 */
public class CD5_2
{
    public static class Solution
    {
        public Stack<Integer> dataStack = new Stack<>();
        public Stack<Integer> minStack = new Stack<>();

        public void push(int data)
        {
            dataStack.push(data);
            if (minStack.isEmpty()) minStack.push(data);
            else if (data <= minStack.peek()) minStack.push(data);
        }

        public void pop()
        {
            if (dataStack.peek().equals(minStack.peek())) minStack.pop();
            dataStack.pop();
        }

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

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        Scanner in = new Scanner(System.in);
        int N = Integer.parseInt(in.nextLine());
        while (N-- > 0)
        {
            String s = in.nextLine();
            if (s.startsWith("push"))
                solution.push(Integer.parseInt(s.split(" ")[1]));
            else if (s.startsWith("pop"))
                solution.pop();
            else
                System.out.println(solution.getMin());
        }
    }
}

CD6 由两个栈组成的队列

/* 模拟 */
public class CD6_1
{
    public static class Solution
    {
        public Stack<Integer> stack1 = new Stack<>();
        public Stack<Integer> stack2 = new Stack<>();

        public void add(int data)
        {
            stack1.add(data);
        }

        public void poll()
        {
            if (stack2.isEmpty())
            {
                while (!stack1.isEmpty())
                    stack2.add(stack1.pop());
            }
            stack2.pop();
        }

        public int peek()
        {
            if (stack2.isEmpty())
            {
                while (!stack1.isEmpty())
                    stack2.add(stack1.pop());
            }
            return stack2.peek();
        }
    }

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        Scanner in = new Scanner(System.in);
        int N = Integer.parseInt(in.nextLine());
        while (N-- > 0)
        {
            String s = in.nextLine();
            if (s.startsWith("add"))
                solution.add(Integer.parseInt(s.split(" ")[1]));
            else if (s.startsWith("poll"))
                solution.poll();
            else
                System.out.println(solution.peek());
        }
    }
}

CD7 如何仅用递归函数和栈操作逆序一个栈

/* 模拟 */
public class CD7_1
{
    public static void solution(Stack<Integer> stack)
    {
        if (stack.isEmpty()) return;
        String prefix = stack.size() == 1 ? "" : " ";
        Integer popNum = stack.pop();
        solution(stack);
        System.out.print(prefix + popNum);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        Stack<Integer> stack = new Stack<>();
        int N = Integer.parseInt(in.nextLine());
        while (N-- > 0)
            stack.add(in.nextInt());
        solution(stack);
    }
}

/* 模拟 */
public class CD7_2
{
    // 取栈底元素并将其删除
    public static int getAndRemoveLast(Stack<Integer> stack)
    {
        if (stack.size() == 1) return stack.pop();
        Integer popNum = stack.pop();
        int last = getAndRemoveLast(stack);
        stack.add(popNum);
        return last;
    }

    public static Stack<Integer> solution(Stack<Integer> stack)
    {
        if (stack.isEmpty()) return stack;
        int last = getAndRemoveLast(stack);
        Stack<Integer> ans = solution(stack);
        ans.add(last);
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        Stack<Integer> stack = new Stack<>();
        int N = Integer.parseInt(in.nextLine());
        while (N-- > 0)
            stack.add(in.nextInt());
        Stack<Integer> res = solution(stack);
        while (!res.isEmpty())
            System.out.print(res.pop() + (res.isEmpty() ? "" : " "));
    }
}

CD100 猫狗队列⭐

/* ⭐利用时间戳⭐ */
public class CD100_1
{
    // 防止运行超时
    public static PrintWriter out = new PrintWriter(System.out);

    public static class Solution
    {
        public static Queue<int[]> catQue = new LinkedList<>();
        public static Queue<int[]> dogQue = new LinkedList<>();
        public static int time = 0;

        public void add(String name, int id)
        {
            if ("cat".equals(name))
                catQue.add(new int[]{time++, id});
            else if ("dog".equals(name))
                dogQue.add(new int[]{time++, id});
        }

        public void pollAll()
        {
            while (!catQue.isEmpty() && !dogQue.isEmpty())
            {
                if (catQue.peek()[0] < dogQue.peek()[0])
                    out.println("cat " + catQue.poll()[1]);
                else
                    out.println("dog " + dogQue.poll()[1]);
            }
            while (!dogQue.isEmpty())
                out.println("dog " + dogQue.poll()[1]);
            while (!catQue.isEmpty())
                out.println("cat " + catQue.poll()[1]);
        }

        public void pollDog()
        {
            while (!dogQue.isEmpty())
                out.println("dog " + dogQue.poll()[1]);
        }

        public void pollCat()
        {
            while (!catQue.isEmpty())
                out.println("cat " + catQue.poll()[1]);
        }

        public String isEmpty()
        {
            return (dogQue.isEmpty() && catQue.isEmpty()) ? "yes" : "no";
        }

        public String isDogEmpty()
        {
            return dogQue.isEmpty() ? "yes" : "no";
        }

        public String isCatEmpty()
        {
            return catQue.isEmpty() ? "yes" : "no";
        }
    }

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        Scanner in = new Scanner(System.in);
        int N = Integer.parseInt(in.nextLine());
        while (N-- > 0)
        {
            String[] s = in.nextLine().split(" ");
            switch (s[0])
            {
                case "add":
                    solution.add(s[1], Integer.parseInt(s[2]));
                    break;
                case "pollAll":
                    solution.pollAll();
                    break;
                case "pollDog":
                    solution.pollDog();
                    break;
                case "pollCat":
                    solution.pollCat();
                    break;
                case "isEmpty":
                    out.println(solution.isEmpty());
                    break;
                case "isDogEmpty":
                    out.println(solution.isDogEmpty());
                    break;
                case "isCatEmpty":
                    out.println(solution.isCatEmpty());
                    break;
            }
        }
        out.flush();
    }
}

CD13 用一个栈实现另一个栈的排序

/* 模拟 */
public class CD13_1
{
    public static Stack<Integer> solution(Stack<Integer> stack)
    {
        Stack<Integer> temp = new Stack<>();
        while (!stack.isEmpty())
        {
            if (temp.isEmpty() || stack.peek() <= temp.peek())
                temp.add(stack.pop());
            else
            {
                Integer popNum = stack.pop();
                while (!temp.isEmpty() && popNum > temp.peek())
                    stack.add(temp.pop());
                temp.add(popNum);
            }
        }
        while (!temp.isEmpty())
            stack.add(temp.pop());
        return stack;
    }

    public static void main(String[] args)
    {
        Stack<Integer> stack = new Stack<>();
        Scanner in = new Scanner(System.in);
        int N = Integer.parseInt(in.nextLine());
        while (N-- > 0)
            stack.add(in.nextInt());
        Stack<Integer> res = solution(stack);
        while (!res.isEmpty())
            System.out.print(res.pop() + (res.isEmpty() ? "" : " "));
    }
}

CD22 用栈来求解汉诺塔问题⭐

/*
* ⭐递归⭐
* 1. 前n-1个盘子从左柱到右柱
* 2. 第n个盘子从左柱到临时柱
* 3. 前n-1个盘子从右柱到左柱
* 4. 第n个盘子从临时柱到右柱
* 5. 前n-1个盘子从左柱到右柱
*/
public class CD22_1
{
    public static int solution(int n, String left, String right, String temp)
    {
        if (n == 0) return 0;
        int p1 = solution(n - 1, left, right, temp);
        System.out.printf("Move %d from %s to %s\n", n, left, temp);
        int p2 = solution(n - 1, right, left, temp);
        System.out.printf("Move %d from %s to %s\n", n, temp, right);
        int p3 = solution(n - 1, left, right, temp);
        return p1 + p2 + p3 + 2;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.printf("It will move %d steps.", solution(n, "left", "right", "mid"));
    }
}

/* 非递归写法 */
public class CD22_2
{
}

CD15 生成窗口最大值数组

/* 单调递减队列 + 滑动窗口 */
public class CD15_1
{
    public static ArrayList<Integer> solution(int[] arr, int N, int W)
    {
        ArrayList<Integer> ans = new ArrayList<>();
        Deque<Integer> que = new LinkedList<>();
        int l = 0, r = 0;
        while (r < N)
        {
            while (r - l < W)
            {
                while (!que.isEmpty() && arr[r] > arr[que.getLast()])
                    que.removeLast();
                que.add(r);
                r++;
            }
            ans.add(arr[que.getFirst()]);
            l++;
            if (l > que.getFirst())
                que.removeFirst();
        }
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, W;
        N = in.nextInt();
        W = in.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = in.nextInt();
        ArrayList<Integer> res = solution(arr, N, W);
        System.out.println(res.stream().map(e -> String.valueOf(e)).collect(Collectors.joining(" ")));
    }
}

CD101 单调栈结构

/* 单调栈(无法处理数组中有相同数值的情况) */
public class CD101_1
{
    public static int[][] solution(ArrayList<Integer> arr)
    {
        Stack<Integer> incStack = new Stack<>();
        int[][] ans = new int[arr.size()][2];
        for (int idx = 0; idx < arr.size(); idx++)
        {
            while (!incStack.isEmpty() && arr.get(idx) < arr.get(incStack.peek()))
            {
                int popIdx = incStack.pop();
                ans[popIdx][0] = incStack.isEmpty() ? -1 : incStack.peek();
                ans[popIdx][1] = idx;
            }
            incStack.add(idx);
        }
        while (!incStack.isEmpty())
        {
            int popIdx = incStack.pop();
            ans[popIdx][0] = incStack.isEmpty() ? -1 : incStack.peek();
            ans[popIdx][1] = -1;
        }
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out); // 防止运行超时
        ArrayList<Integer> arr = new ArrayList<>();
        int N = in.nextInt();
        while (N-- > 0)
            arr.add(in.nextInt());
        int[][] res = solution(arr);
        for (int[] temp : res)
            out.println(temp[0] + " " + temp[1]);
        out.flush();
    }
}

CD188 单调栈结构（进阶）⭐

/* ⭐单调栈(解决CD101的问题)⭐ */
public class CD188_1
{
    public static int[][] solution(ArrayList<Integer> arr)
    {
        Stack<Integer> incStack = new Stack<>();
        ArrayList<Integer> temp = new ArrayList<>();
        int[][] ans = new int[arr.size()][2];
        for (int idx = 0; idx < arr.size(); idx++)
        {
            while (!incStack.isEmpty() && arr.get(idx) < arr.get(incStack.peek()))
            {
                int popIdx = incStack.pop();
                temp.clear();
                temp.add(popIdx);
                while (!incStack.isEmpty() && arr.get(popIdx).equals(arr.get(incStack.peek())))
                    temp.add(incStack.pop());
                for (int i : temp)
                {
                    ans[i][0] = incStack.isEmpty() ? -1 : incStack.peek();
                    ans[i][1] = idx;
                }
            }
            incStack.add(idx);
        }
        while (!incStack.isEmpty())
        {
            int popIdx = incStack.pop();
            temp.clear();
            temp.add(popIdx);
            while (!incStack.isEmpty() && arr.get(popIdx).equals(arr.get(incStack.peek())))
                temp.add(incStack.pop());
            for (int i : temp)
            {
                ans[i][0] = incStack.isEmpty() ? -1 : incStack.peek();
                ans[i][1] = -1;
            }
        }
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out); // 防止运行超时
        ArrayList<Integer> arr = new ArrayList<>();
        int N = in.nextInt();
        while (N-- > 0)
            arr.add(in.nextInt());
        int[][] res = solution(arr);
        for (int[] temp : res)
            out.println(temp[0] + " " + temp[1]);
        out.flush();
    }
}

CD16 求最大子矩阵的大小⭐

/* ⭐单调栈⭐ */
public class CD16_1
{
    public static int solution(int[][] arr)
    {
        int ans = Integer.MIN_VALUE;
        int[] height = new int[arr[0].length];
        for (int[] ints : arr)
        {
            for (int i = 0; i < arr[0].length; i++)
                height[i] = ints[i] == 1 ? height[i] + 1 : 0;
            ans = Math.max(ans, calMaxRec(height));
        }
        return ans;
    }

    public static int calMaxRec(int[] height)
    {
        int ans = Integer.MIN_VALUE, width;
        Stack<Integer> incStack = new Stack<>();
        for (int i = 0; i < height.length; i++)
        {
            while (!incStack.isEmpty() && height[i] < height[incStack.peek()])
            {
                int popIdx = incStack.pop();
                while (!incStack.isEmpty() && height[popIdx] == height[incStack.peek()])
                    incStack.pop();
                width = (i - 1) - (incStack.isEmpty() ? 0 : incStack.peek() + 1) + 1;
                ans = Math.max(ans, height[popIdx] * width);
            }
            incStack.add(i);
        }
        while (!incStack.isEmpty())
        {
            Integer popIdx = incStack.pop();
            width = (height.length - 1) - (incStack.isEmpty() ? 0 : incStack.peek() + 1) + 1;
            ans = Math.max(ans, height[popIdx] * width);
        }
        return ans;
    }

    public static void main(String[] args)
    {
        int N, M;
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        int[][] arr = new int[N][M];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                arr[i][j] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD18 最大值减去最小值小于或等于 num 的子数组数量⭐

/*
 * ⭐单调队列⭐
 * 若a[i...j]符合要求, 那么a[i...l]都符合要求(i<=l<=j)
 * 若a[i...j]不符合要求, 那么a[i...l]都不符合要求(l>j)
 */
public class CD18_1
{
    public static int solution(int[] arr, int NUM)
    {
        int len = arr.length, i = 0, j = 0, ans = 0;
        Deque<Integer> incStack = new LinkedList<>();
        Deque<Integer> decStack = new LinkedList<>();
        while (i < len)
        {
            while (j < len)
            {
                while (!incStack.isEmpty() && arr[j] <= arr[incStack.getLast()])
                    incStack.removeLast();
                incStack.addLast(j);
                while (!decStack.isEmpty() && arr[j] >= arr[decStack.getLast()])
                    decStack.removeLast();
                decStack.addLast(j);
                if (arr[decStack.getFirst()] - arr[incStack.getFirst()] > NUM)
                    break;
                j++;
            }
            ans += j - i;
            if (i == incStack.peekFirst()) incStack.removeFirst();
            if (i == decStack.peekFirst()) decStack.removeFirst();
            i++;
        }
        return ans;
    }

    public static void main(String[] args)
    {
        int N, NUM;
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        NUM = in.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr, NUM));
    }
}

CD102 可见的山峰对数量❗

/* ❗思维题❗ */
public class CD102_1
{
    public static void main(String[] args)
    {
        int T, n, p, m;
        Scanner in = new Scanner(System.in);
        T = in.nextInt();
        while (T-- > 0)
        {
            n = in.nextInt();
            p = in.nextInt();
            m = in.nextInt();
            System.out.println(Math.max(0, 2 * n - 3));
        }
    }
}

CD105 可见的山峰对数量（进阶）❗

/* ❗单调栈❗ */
public class CD105_1
{
    public static int solution(int[] arr)
    {
        if (arr == null || arr.length < 2) return 0;
        int size = arr.length;
        int maxIndex = 0;
        for (int i = 0; i < size; i++)
            maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex;
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{arr[maxIndex], 1});
        int index = nextIndex(maxIndex, size);
        int res = 0;
        while (index != maxIndex)
        {
            while (stack.peek()[0] < arr[index])
            {
                int k = stack.pop()[1];
                res += getInternalSum(k) + 2 * k;
            }
            if (stack.peek()[0] == arr[index])
                stack.peek()[1]++;
            else
                stack.push(new int[]{arr[index], 1});
            index = nextIndex(index, size);
        }
        while (stack.size() > 2)
        {
            int times = stack.pop()[1];
            res += getInternalSum(times) + 2 * times;
        }
        if (stack.size() == 2)
        {
            int times = stack.pop()[1];
            res += getInternalSum(times) + (stack.peek()[1] == 1 ? times : 2 * times);
        }
        res += getInternalSum(stack.pop()[1]);
        return res;
    }

    public static int getInternalSum(int k)
    {
        return k == 1 ? 0 : (k * (k - 1) / 2);
    }

    public static int nextIndex(int i, int size)
    {
        return i < (size - 1) ? (i + 1) : 0;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] m = new int[N];
        for (int i = 0; i < N; i++)
            m[i] = in.nextInt();
        System.out.println(solution(m));
    }
}