算法题高阶

二重式

分治法

中位数

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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]

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

思路:

  1. 如果数组元素非负, 那么可以直接求以每个元素为最小值的最大区间. 维护一个单调非增的栈
  2. 如果元素任意,找到区间之后再逐个求.
    现假定是第一种情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)算法介绍