题目来源:https://leetcode.com/problems/odd-even-jump/description/

标记难度:Hard

提交次数:2/2

代码效率:

  • 单调栈:100.00%(72ms)
  • 平衡树:60.56%(100ms)

题意

We need to jump higher and lower alternately to the end. [1]

这句题目描述太精妙了,以至于我深感自己理解能力和语言描述能力的匮乏。

简单来说就是,从数组的某个index出发,先跳到它后面的比它大的元素中最小的元素(如果有相同元素则选择最靠左的一个),再跳到它后面的比它小的元素中最大的元素(相同时仍然选择最靠左的一个),交替采取这两种跳法,直到跳不动了为止。问从多少个index出发可以最终跳到最后一个元素。

分析

法一:单调栈

我在做题之前得到了一点提示(这道题应该用栈来做),遂在一通魔调之后搞出了一个能过的单调栈解法。说起来,我还是看了这次的题解才知道这种方法的名字应该叫单调栈(monotonic stack)。于是我决定把之前用这个算法的文章的标签修改一下……

和之前的那些单调栈相比,这次的做法没什么大的差异,但解决平局的方法有所不同。以index为第二关键字对数组排序之后,找右侧更大的数的时候,需要倒序遍历数组,单调栈正好可以处理平局的问题;但找右侧更小的数的时候,正序遍历数组,对于大小相同的数,index较小的先出现,较大的后出现,之后的数就找不到index较小的数了。

所以找右侧更小的数的时候,需要把大小相同的数按index倒序排序。

单调栈中index的大小和左右侧有关,排序的顺序和大小有关。

法二:平衡树

但是实际上我已经做单调栈的题太多以至于过拟合了。之前我还会想到平衡树的解法的……现在已经只会单调栈啦!!![1]

结果在这个解法上还是遇到了问题。第一个问题就是不要用std::upper_bound,要用map.upper_bound(针对内部容器实现的,和针对map实现的区别)。第二个问题是,题目要求是带等号的,而upper_bound找不到等号,所以要修改一下得到的结果。

代码

单调栈

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
int oddEvenJumps(vector<int>& A) {
int n = A.size();
int odd[n], even[n];

stack<pair<int, int>> s;
vector<pair<int, int>> indices;
for (int i = 0; i < n; i++)
indices.emplace_back(A[i], -i);
sort(indices.begin(), indices.end());
for (int i = 0; i < n; i++)
indices[i].second = -indices[i].second;
for (int i = 0; i < n; i++) {
while (!s.empty() && indices[i].second > s.top().second) {
s.pop();
}
if (s.empty())
even[indices[i].second] = -1;
else
even[indices[i].second] = s.top().second;
s.push(indices[i]);
}

s = stack<pair<int, int>>();
indices.clear();
for (int i = 0; i < n; i++)
indices.emplace_back(A[i], i);
sort(indices.begin(), indices.end());
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && indices[i].second > s.top().second)
s.pop();
if (s.empty())
odd[indices[i].second] = -1;
else
odd[indices[i].second] = s.top().second;
s.push(indices[i]);
}

int oddjump[n], evenjump[n];
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
if (odd[i] != -1) oddjump[i] = evenjump[odd[i]];
else oddjump[i] = i;
if (even[i] != -1) evenjump[i] = oddjump[even[i]];
else evenjump[i] = i;
if (oddjump[i] == n - 1) ans++;
}
return ans;
}
};

平衡树

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
class Solution {
public:
int oddEvenJumps(vector<int>& A) {
int n = A.size();
int odd[n], even[n];
even[n-1] = odd[n-1] = n - 1;

int ans = 1;
map<int, int> treeSet;
treeSet[A[n-1]] = n - 1;
for (int i = n - 2; i >= 0; i--) {
auto si = treeSet.upper_bound(A[i]);
auto bi = treeSet.lower_bound(A[i]);
if (si != treeSet.begin())
even[i] = odd[(--si)->second];
else
even[i] = -1;
if (bi != treeSet.end())
odd[i] = even[bi->second];
else
odd[i] = -1;
treeSet[A[i]] = i;
if (odd[i] == n - 1) ans++;
}

return ans;
}
};

  1. lee215's solution for 975 - [Java/C++/Python] DP idea, Using TreeMap or Stack

题目来源:https://leetcode.com/problems/largest-rectangle-in-histogram/description/

标记难度:Hard

提交次数:1/3

代码效率:

  • O(N^2)递推:超时
  • 单栈:98.96%

题意

给定一个直方图的高度(或者说给定一排宽度都为1的矩形柱子的高度),找出图中包含的面积最大的矩形。

分析

显然可以有这样的直觉:所能找到的面积最大的矩形必定与某个矩形柱子的高度是相等的,否则它的高度必然小于它覆盖的所有柱子,因此高度还可以再升高,直到到达某个柱子的高度为止。因此问题可以转化为,对于每个柱子,它左边和右边各有多少个连续的柱子的高度不小于它?不妨记这两个值为left[i]right[i],则以第i个柱子为最大高度的矩形的面积就是(left[i] + right[i] + 1) * heights[i]

我的第一个解法是错误的:试图直接通过前一个柱子的left[i-1]推导出下一个柱子的left[i]。显然这两者并不存在一个直接的推导关系,所以我WA了。

于是我立刻想出了第二种解法——用O(N^2)的复杂度直接计算leftright数组。题目里没给N的范围,不过我还是TLE了。

这时候我才想起来,我已经见过三道类似的题目了,它们分别是:

它们所需要完成的任务是相似的:给定一个数组,为其中的每个数求出它左边/右边/both的第一个比它大/小的数的位置。这种算法我已经详细分析过了,所以现在不妨来比较一下这几道题的区别,特别是有重复数字时的边界问题的处理。下面用A表示数组:

  • Leetcode 901:求左侧第一个> A[i]的值。
  • Leetcode 739:求右侧第一个> A[i]的值。
  • Leetcode 907:在问题的转换过程中需要自行确定边界:
    • 计算“以A[i]为最小值的子序列的数量”之前,就需要考虑一个子序列中有多个最小值的情况怎么办。显然一个子序列只能被作为其中一个最小值所对应的子序列计算一次。所以问题是应该选择哪一个最小值作为“最小值”。显然比较方便的办法是取最左边或最右边的最小值。
    • 如果取的是最左边的最小值,则对于每个值,需要求的是左侧第一个<= A[i]的值,和右侧第一个< A[i]的值;
    • 反之,则需要求左侧第一个< A[i]的值,和右侧第一个<= A[i]的值。
  • Leetcode 84:求左侧第一个< A[i]的值,和右侧第一个< A[i]的值。

Leetcode 907的分析中已经提到,有两种做法,一种是用两次迭代分别求左侧和右侧的值;另一种是直接用一次迭代。这种方法很聪明,但面临着一个问题:它无法实现左右两侧都严格不等或都不严格不等的情况。考虑用这一算法实现的907题,假如在栈中,A[i]将要被A[j]弹出了:

  • 如果条件是A[i] >= A[j],则对于A[j],它将找到左侧第一个< A[j]的值,但对于A[i],它找到的是右侧第一个<= A[i]的值
  • 如果条件是A[i] > A[j],则A[j]找到的是左侧第一个<= A[j]的值,但A[i]找到的是右侧第一个< A[i]的值

我想这是算法本身的限制。(也许可以改进,但我现在不太想思考了)所以严格来说,单栈算法对本题之前的模型是不太合适的。

但是我还是用了单栈的算法,因为可以把模型改一下。假如最大的矩形碰到了至少两个柱子的边界,说明对于这些柱子,它们都能计算得到对应的矩形面积(按照之前的算法)。那么只要保证其中至少一根柱子在计算的时候得到正确结果即可(其他的可以不管)。于是问题就转化成类似于907题的情况了。

代码

O(N^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
25
26
27
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
if (n == 0) return 0;
if (n == 1) return heights[0];

vector<int> sorted(heights);
sort(sorted.begin(), sorted.end());
long long int f[n];
memset(f, 0, sizeof(f));
long long int ans = 0;
// for each rectangle
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (sorted[j] > heights[i])
f[j] = 0;
else {
f[j]++;
ans = max(ans, f[j] * sorted[j]);
}
}
}

return ans;
}
};

单栈

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
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
if (n == 0) return 0;
if (n == 1) return heights[0];

stack<pair<int, int>> s; // height, pos
// Note: the left and right arrays are defined slightly differently
// - They denote positions, not length (not a big deal though)
long long int left[n], right[n], ans = 0;
for (int i = 0; i < n; i++) {
while (!s.empty() && s.top().first > heights[i]) {
right[s.top().second] = i;
s.pop();
}
if (s.empty()) left[i] = -1;
else left[i] = s.top().second;

s.emplace(heights[i], i);
}
while (!s.empty()) {
right[s.top().second] = n;
s.pop();
}

for (int i = 0; i < n; i++)
ans = max(ans, (right[i] - left[i] - 1) * heights[i]);

return ans;
}
};

题目来源:https://leetcode.com/problems/sum-of-subarray-minimums/description/

标记难度:Medium

提交次数:3/5

代码效率:

  • BST:304ms
  • 2 Stacks:60ms
  • 1 Stack:84ms

题意

给定正整数数组A,求出A中所有连续子序列的最小值之和mod (10^9 + 7)

分析

比赛后再看到题解时,我的内心是震惊的。没错,这道题又是一道和Leetcode 901一样的题。比赛期间我使用了原来想到的那种O(n * log(n))的BST方法,完全没有意识到这道题和前一晚上学习的题解的相似性。于是我对自己的学习情况表示了深切的怀疑。


显然一种较好的思路是,对于A中的每一个值A[i],寻找以它为最小值的子序列的数量。也就是说,我们需要寻找A[i]左侧第一个比它大的值的位置,以及右侧第一个比它大的值的位置。然后就可以计算对应的子序列的数量了。

显然这个寻找的过程和刚才说到的题是一样的,因此就不多写了。[1]

这个过程可以简化为使用一个栈。对于被某个数从栈中弹出的数而言,它右侧第一个比它小的数就是这个数。所以我们可以对所有被弹出的数得到左侧的区间范围和右侧的区间范围。我觉得这是一种非常聪明的做法。[2]

代码

BST

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
38
39
40
class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
vector<pair<int, int>> loc;
int n = A.size();
for (int i = 0; i < n; i++)
loc.emplace_back(A[i], i);
sort(loc.begin(), loc.end());
set<int> locSet;

long long int sum = 0;
for (int i = 0; i < n; i++) {
int index = loc[i].second;
long long int val = loc[i].first;
int left = 0;
int right = 0;

auto it = locSet.lower_bound(index);
if (it != locSet.begin()) {
--it;
left = index - *it - 1;
}
else
left = index;

it = locSet.upper_bound(index);
if (it != locSet.end()) {
right = *it - index - 1;
}
else
right = n - index - 1;

sum += val * (left + 1) * (right + 1) % 1000000007;
sum %= 1000000007;
locSet.insert(index);
}

return sum;
}
};

2 Stacks

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
38
39
40
41
42
43
class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
stack<pair<int, int>> leftStack, rightStack;
int n = A.size();
int left[n], right[n];

leftStack.emplace(-1, -1); // val, idx
for (int i = 0; i < n; i++) {
while (!leftStack.empty() && leftStack.top().first >= A[i])
leftStack.pop();
if (leftStack.top().second == -1)
left[i] = i;
else
left[i] = i - leftStack.top().second - 1;

leftStack.emplace(A[i], i);
}

rightStack.emplace(-1, -1);
for (int i = n - 1; i >= 0; i--) {
// 对于leftStack,此处写的是>=
// 这意味着对于同一子序列中有多个最小元素的情况,
// 我们选择把这种情况的值最右侧的最小元素中计算。
// (防止重复计算)
while (!rightStack.empty() && rightStack.top().first > A[i])
rightStack.pop();
if (rightStack.top().second == -1)
right[i] = n - i - 1;
else
right[i] = rightStack.top().second - i - 1;

rightStack.emplace(A[i], i);
}

long long int sum = 0;
for (int i = 0; i < n; i++) {
sum += (left[i] + 1) * (right[i] + 1) * (long long int) A[i] % 1000000007;
sum %= 1000000007;
}
return sum;
}
};

1 Stack

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
class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
stack<pair<int, int>> s; // (ele, idx)
long long int sum = 0;
int n = A.size();
for (int i = 0; i <= n; i++) {
// 我经常想不清楚这个地方的符号。不过,当A[i] > 已有元素时,
// 并不会影响那些元素作为最小值。这样想比较容易。
if (s.empty() || i < n && s.top().first <= A[i])
s.emplace(A[i], i);
else {
while (!s.empty() && (i == n || s.top().first > A[i])) {
int val = s.top().first;
int idx = s.top().second;
s.pop();
int left, right;
if (s.empty()) left = idx;
else left = idx - s.top().second - 1;
right = i - idx - 1;

sum += (long long) (left + 1) * (right + 1) * val % 1000000007;
sum %= 1000000007;
}
s.emplace(A[i], i);
}
}
return sum;
}
};

  1. [C++/Java/Python] Stack Solution

  2. One stack solution

题目来源:https://leetcode.com/problems/daily-temperatures/description/

标记难度:Medium

提交次数:3/6

代码效率:

  • 排序+BST:14.41%
  • 栈:58.54%
  • 暴力:48.92%

题意

Leetcode 901差不多,不过顺序正好相反。

分析

因为是几乎一样的所以没什么好分析的。但是在这道题中,因为数据范围比较小([30, 100]),所以可以从右往左扫描,维护每个温度出现的最左侧的位置,然后对当前的温度,遍历比它高的所有温度,找出其中位于最左侧的。这大概是一种暴力算法吧。[1]

代码

离线算法:排序+BST

虽然写了计数排序,但这个算法仍然超时了。一般来说,30000规模的数据用O(n * log(n))的算法没有什么太大的问题,此处不知道是因为用的STL太多了,Leetcode太面向对象了,还是Leetcode的评测机太渣了。既然如此,纯递归的算法更没有写的必要……

2018.9.16 UPDATE:我错怪Leetcode了,实际上是我自己没用对set.lower_bound,结果变成了O(n^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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
private:
struct Pair {
int val;
int index;

Pair(int v, int i) {
val = v;
index = i;
}

friend bool operator < (const Pair& x, const Pair& y) {
if (x.val != y.val) return x.val < y.val;
return x.index > y.index;
}
};

void bucketSort(vector<Pair>& a) {
list<Pair> bucket[105];
for (int i = 0; i < a.size(); i++) {
bucket[a[i].val].push_front(a[i]);
}
int n = 0;
for (int i = 30; i <= 100; i++) {
for (auto j = bucket[i].begin(); j != bucket[i].end(); j++){
a[n++] = *j;
}
}
}

public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<Pair> loc;
int n = temperatures.size();
vector<int> ans(n);
for (int i = 0; i < n; i++) {
loc.emplace_back(temperatures[i], i);
}
// sort(loc.begin(), loc.end());
bucketSort(loc);
set<int> indSet;

for (int i = n - 1; i >= 0; i--) {
// auto it = lower_bound(indSet.begin(), indSet.end(), loc[i].index);
// 上面那个写法是错误的,因为std::lower_bound函数并不知道set的内部结构
// 下面使用std::set::lower_bound才是正确的
auto it = indSet.lower_bound(loc[i].index);
if (it == indSet.end())
ans[loc[i].index] = 0;
else
ans[loc[i].index] = *it - loc[i].index;
indSet.insert(loc[i].index);
}
return ans;
}
};

在线算法:栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<pair<int, int>> s;
int n = temperatures.size();
vector<int> ans(n);
s.emplace(1000, -1); // 一个哨兵
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && s.top().first <= temperatures[i])
s.pop();
if (s.top().second == -1) ans[i] = 0;
else ans[i] = s.top().second - i;
s.emplace(temperatures[i], i);
}
return ans;
}
};

在线算法:暴力

如果要求在线,数据从右向左提供,则显然暴力算法是可以在线的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
int lastIdx[105];
vector<int> ans(n, 0);
for (int i = 0; i < 105; i++)
lastIdx[i] = n;
for (int i = n - 1; i >= 0; i--) {
int minn = n;
for (int j = temperatures[i] + 1; j <= 100; j++)
minn = min(minn, lastIdx[j]);
if (minn == n)
ans[i] = 0;
else
ans[i] = minn - i;
lastIdx[temperatures[i]] = i;
}
return ans;
}
};

  1. Leetcode 739 Solution

题目来源:https://leetcode.com/problems/online-stock-span/description/

标记难度:Medium

提交次数:1/1

代码效率:19.81%

题意

给定一个整数数组,为每一个数求出以它为结尾的满足这一条件的连续子数组的最大长度:其余的数都比它更小。

分析

比赛的时候显然我没有做出来这道题,心态崩了。我大概是想出了一个合理的离线方法,但这道题强制要求在线。我当时只能想出O(n^2)的暴力在线方法,没看出来什么递推的方法简化时间复杂度。或者说我就没见过这个类型的题目……


离线算法1:排序

如果这道题是离线的话,我想出了这样一种做法:

  • 首先把所有数和它们原来的index进行排序
  • 然后按数值大小遍历所有数,并维护一棵存放index的BST;对于每个数,在该BST中查找自己的index的前驱,前驱和自己的index之间的距离(有相同数值时需要特殊处理);最后把自己的index插入树中

时间复杂度是O(n * log(n))

离线算法2:递归

事实上通过仔细观察是可以进行一定程度的递推的。这一点我觉得题解就写得不错。假定当前的数组是这样的:

1
2
array = [11, 3, 9, 5, 6, 4]
len = [ 1, 1, 2, 1, 2, 1]

对于下一个元素x

  • 如果x < last,则len[x] = 1
  • 如果x == last,则len[x] = len[last] + 1
  • 如果x > last,则需要在前面的元素中找到比x大的最后一个元素。不过,因为x > last,所以需要找到的元素必然也比last更大。所以对于每一个元素,只有前面比它更大的元素在递推中才有意义。

但是这么想还不够好,因为显然元素的大小可能是随机的,对于不同的元素,“前面比它更大的元素”这个集合在动态变化,并不能直接进行递推。

再重新观察一下上面的例子,查看一下每个元素覆盖的具体子序列:

1
2
3
4
5
6
7
array =     [ 11, 3 , 9 , 5 , 6 , 4 ]
Element 11 +
Element 3 +
Element 9 + +
Element 5 +
Element 6 + +
Element 4 +

一个有趣的问题是,可以试图从这些元素中选择出一部分,使得它们各自的子序列恰好可以拼成这个完整的数组。选择的方法是,先选出数组中最大的数,再选出数组中在这个数之后最大的数,再选出在这个数之后最大的数……直到选到最后一个数。在这个例子中,选出的就是11, 9, 6, 4。它们对应的子序列的长度就是到前一个数的距离。

那么在选出来的数中间的那些数怎么办呢?事实上,这个时候我们已经得到了一个子问题的结构。通过上述选择过程可以看出,夹在选出来的数中间的数必然比两边的数小,也就是说它们的子序列长度和周围的数没有任何关系。

但这仍然是一个离线算法,而且时间复杂度也很成问题。

在线算法:栈

事实上我刚才写了那么多字,主要是为了试图解释这个算法为何是合理的——因为我看到题解的时候,实在是不知道为什么能这么做。不过现在我觉得我已经可以给出一个合理的答案了。刚才已经得到了一个子问题的结构。虽然看起来好像一次选择可能会把数组划分成好几个子问题(事实上也是这样),但实际上并没有把这个问题递归化的必要——因为分割前的元素的结果不依赖于子问题的结果,对吧。所以只要能合理地划分子问题,就可以用任意合理的顺序来解决子问题——比如顺序解决。

我想,栈的作用就是这样的。在加入每个元素之前,把比它小的元素都弹出来。此时栈中实际上顺序保存了一些子问题的元素。(我发现很难描述到底保存了哪些元素……)弹出的过程相当于解决了当前层次的所有子问题。题解中只说“关注递增的元素”,但并没有解释怎么关注递增的元素这个问题。[1]

PS. 这道题和Leetcode 739基本上是一样的,看来我还是见得少了。

2018.9.16 UPDATE:通过今天的比赛题Leetcode 907,我意识到了一个问题,这个算法比我想象得要更强一些。对于被某个数从栈中弹出的数而言,它右侧第一个比它大的数就是这个数。所以一个方向的一次使用栈的操作可以同时解决两侧的问题。

代码

只实现了在线算法(显然只能这样)。

在线算法:栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class StockSpanner {
private:
stack<pair<int, int>> s;

public:
StockSpanner() { }

int next(int price) {
int sum = 1;
while (!s.empty() && s.top().first <= price) {
sum += s.top().second;
s.pop();
}
s.emplace(price, sum);
return sum;
}
};

  1. Leetcode 901 Solution