算法题高阶

二重式

分治法

中位数

运用彩虹排序的思想,把数组分为三个区域,分别为大于,等于,小于pivot的.

public class Solution {
    /**
     * @param nums: A list of integers.
     * @return: An integer denotes the middle number of the array.
     */
    public int median(int[] nums) {
        // write your code here
        int size = nums.length % 2 == 0 ? nums.length / 2 - 1 : nums.length / 2;
        return findK(nums, 0, nums.length - 1, size);
    }
    private int findK(int[] num, int start, int end, int mid) {
        int i = start, j = start;
        int k = end;
        int pivot = num[start];
        while (j <= k) {
            if (num[j] < pivot) {
                swap(num, i++, j++);
            } else if (num[j] > pivot) {
                swap(num, j, k--);
            } else {
                j++;
            }
        }
        if (i > mid) {
            return findK(num, start, i - 1, mid);
        } else if (k < mid) {
            return findK(num, k + 1, end, mid);
        } else {
            return num[mid];
        }
    }
    private void swap(int[] num, int i, int j) {
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }
}

单调栈

单调栈，顾名思义就是说栈内的元素，按照某种方式排序下，必须是单调的。如果新入栈的元素破坏了单调性，就弹出栈内元素，直到满足单调性。

单调栈: 到底什么时候该用？
答: 在一个线性数据结构中，
为任意一个元素找左边和右边第一个比自己大/小的位置，用单调栈
为任意一个元素找左边最大的和右边最大的位置，用two pointers

单调栈是一个维护型的数据结构，我觉得面试的时候你跟面试官说你打算怎么维护他即可，说出了“单调栈“这个词反而显得你做过这道题。这个概念有点像DP，你忽然说了一个“背包型动态规划”反而会引起别人的警觉，觉得你是老司机刷过这道题

右边第一个大数

对于一个数组中的所有元素, 求出右边第一个比该元素大的数的位置. 如果右边不存在比该元素大的数,返回-1;
例:
[3,1,5,2,4,6]
[2,2,5,4,5,-1]

维护一个单调非增的栈, 如果栈为空或者小于等于栈顶元素,就可以入栈,否则就把之前比该元素都小的元素都出栈,并且计算相应的返回值.

public class FindFirstGreaterNum {
    private int[] findFirstGreaterNum(int[] num) {
        if (num == null || num.length == 0) {
            return null;
        }
        int[] res = new int[num.length];
        Arrays.fill(res, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < num.length; i++) {
            while (!stack.isEmpty() && num[stack.peek()] < num[i]) {
                res[stack.pop()] = i;
            }
            stack.push(i);
        }
        return res;
    }
}

Largest Rectangle in Histogram[https://leetcode.com/problems/largest-rectangle-in-histogram/description]

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int area = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i <= heights.length; i++) {
            int h = i == heights.length ? 0 : heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] > h) {
                int curr = heights[stack.pop()];
                int len = stack.isEmpty() ? i : i - stack.peek() - 1;
                area = Math.max(area, curr * len);
            }
        }
        return area;
    }
}

最大区间权值

区间权值定义为区间内最小的数*区间和
比如 [3,1,6] 一共有6个子区间, 权值分别是:
[3] 9
[1] 1
[6] 36
[3,1] 4
[1,6] 6
[3,1,6] 10

思路:

如果数组元素非负, 那么可以直接求以每个元素为最小值的最大区间. 维护一个单调非增的栈
如果元素任意,找到区间之后再逐个求.
现假定是第一种情况

public class MaxWeight {
    public int findMaxWeight(int num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        int[] prefixSum = new int[num.length + 1];
        for (int i = 1; i <= num.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + num[i - 1];
        }
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i <= num.length; i++) {
            int curr = i == num.length ? 0 : num[i];
            while (!stack.isEmpty() && num[stack.peek()] > curr) {
                int minNum = stack.pop();
                int prev = stack.isEmpty() ? -1 : stack.peek();
                int sum = prefixSum[i] - prefixSum[prev + 1];
                max = Math.max(max, sum * minNum);
            }
            stack.push(i);
        }
        return max;
    }
}

构造MaxTree

给定一个没有重复元素的数组A，定义A上的MaxTree如下：MaxTree的根节点为A中最大的数，根节点的左子树为数组中最大数左边部分的MaxTree，右子树为数组中最大数右边部分的MaxTree。请根据给定的数组A，设计一个算法构造这个数组的MaxTree。

答：
如果能够确定每个节点的父亲节点，则可以构造出整棵树。找出每个数往左数第一个比他大的数和往右数第一个比他大的数，两者中较小的数即为该数的父亲节点。如：[3,1,2]，3没有父亲节点，1的父亲节点为2，2的父亲节为3。并且可以根据与父亲的位置关系来确定是左儿子还是右儿子。接下来的问题是如何快速找出每个数往左、往右第一个比他大的数。这里需要用到数据结构栈。以找每个数左边第一个比他大的数为例，从左到右遍历每个数，栈中保持递减序列，新来的数不停的Pop出栈顶直到栈顶比新数大或没有数。以[3,1,2]为例，首先3入栈，接下来1比3小，无需pop出3，1入栈，并且确定了1往左第一个比他大的数为3。接下来2比1大，1出栈，2比3小，2入栈。并且确定了2往左第一个比他大的数为3。用同样的方法可以求得每个数往右第一个比他大的数。时间复杂度O(n)，空间复杂度也是O(n)为最优解法。

并查集

并查集(Union-Find)算法介绍