1002. Find Common Characters

标记难度:Easy

提交次数:1/1

代码效率:36ms

题意

给你一堆字符串,找到最大的重复字符的数量。相同的字符可以重复算。

分析

最近Leetcode这个题目编号有点乱。

不过这绝对是道水题,统计了每个字符串中每个小写字母的数量之后一起取min即可……

代码

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<string> duplicates(vector<string>& A) {
map<int, int> charMap[105];
for (int i = 0; i < A.size(); i++) {
for (char x: A[i])
charMap[i][x - 'a']++;
}
int minn[26];
for (int i = 0; i < 26; i++)
minn[i] = 1e9;
for (int i = 0; i < A.size(); i++)
for (int j = 0; j < 26; j++)
minn[j] = min(minn[j], charMap[i][j]);
vector<string> ans;
for (int j = 0; j < 26; j++)
for (int i = 0; i < minn[j]; i++)
ans.push_back(string(1, char ('a' + j)));
return ans;
}
};

1003. Check If Word Is Valid After Substitutions

标记难度:Medium

提交次数:1/1

代码效率:

  • 非常暴力的代码:1948ms
  • 一般暴力的代码:80ms
  • 使用栈的代码:20ms

题意

如下定义合法字符串V

  • "abc"是合法字符串
  • 如果V是合法字符串且V = X + YXY均可为空),则X + "abc" + Y为合法字符串

判断给定字符串是否是合法字符串。

分析

显然可以直接写一个暴力方法:每当找到一个"abc",就把它删掉。(而且可以递归删)

稍微好一点的方法是一次多删几个,因为合法的"abc"之间是不会overlap的。

更好的方法是用栈。[1]

代码

非常暴力的代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
bool bnfValid(string S) {
if (S.size() <= 3)
return S == "abc";
int n = S.size();
for (int i = 0; i < n - 3; i++)
if (S.substr(i, 3) == "abc")
return bnfValid(S.substr(0, i) + S.substr(i + 3, n - i - 3));
return false;
}
};

一般暴力的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool isValid(string S) {
while (true) {
string a;
for (char c: S) {
if (a.length() >= 2 && c == 'c' && a.substr(a.size() - 2, 2) == "ab")
a = a.substr(0, a.size() - 2);
else
a += c;
}
if (a.length() <= 3) return a.length() == 0;
if (a == S) return false;
S = a;
}
return true;
}
};

使用栈的代码

其实我觉得这个是正解,上一个代码的本质就是这样的……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
bool isValid(string S) {
vector<char> s;
for (char c: S) {
if (c == 'c' && s.size() >= 2 && s[s.size() - 1] == 'b' && s[s.size() - 2] == 'a') {
s.pop_back();
s.pop_back();
}
else
s.push_back(c);
}
return s.size() == 0;
}
};

1004. Max Consecutive Ones III

标记难度:Medium

提交次数:1/1

代码效率:68ms

题意

给定一个01串,可以把其中最多K个0改成1,问改完之后最长的全1子串的长度。

分析

这显然是个滑动窗口的题目。但问题是怎么写比较好。

我的第一个idea是把连续的01都合并起来,然后去弄滑动窗口。结果我从今天凌晨两点一直调到了三点,这说明我的这个idea本质上可能是非常傻逼的……(当然也可能是凌晨三点不宜写代码。)

今天看了看lee215的代码,深感自己之傻逼,为啥人家不到十行就写好了……(因为lee出了第四题啊人家就是吊啊)

不过既然时间不多,我也不再把他的代码抄一遍了,也许:

  • 把连续问题化成离散问题不一定是好事
  • 滑动窗口维护前沿不变和后沿不变,写法可能会有些差异

代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
private:
int calc(vector<pair<int, int>>& b, int start, int end, int sum, int left) {
int x = 0;
if (end < b.size() && b[end].first == 0) x += b[end].second;
if (b[start].first == 0) x += b[start].first;
else if (start > 0 && b[start - 1].first == 0) x += b[start - 1].second;
return sum + min(left, x);
}

public:
int longestOnes(vector<int>& A, int K) {
// 合并连续01
vector<pair<int, int>> b; // 0/1, cnt
for (int x: A)
if (b.size() == 0 || b.back().first != x)
b.emplace_back(x, 1);
else
b.back().second++;
int left = K;
int end = 0;
int sum = 0;
int ans = -1;
// i是起始位置,end是结束位置,[i, end)
// sum是当前连续1的数量,left是还没有用来填充0的1的数量
// 不过sum是不包括零散的1的……(所以才需要calc函数)
end = -1;
for (int i = 0; i < b.size(); i++) {
// 如果i已经超过了当前的结束位置,那么不如另起炉灶,或者干脆不要从i开始的连续的1算了……
if (i >= end) {
end = i;
sum = 0;
left = K;
while (end < b.size()) {
if (b[end].first == 1) {
sum += b[end].second;
}
else {
if (left >= b[end].second) {
left -= b[end].second;
sum += b[end].second;
}
else break;
}
end++;
}
}
// 删除窗口开头元素
else if (i >= 0 && b[i - 1].first == 1) {
sum -= b[i - 1].second;
}
else if (i >= 0 && b[i - 1].first == 0) {
sum -= b[i - 1].second;
left += b[i - 1].second;
}
// 更新窗口结尾位置
while (end < b.size()) {
if (b[end].first == 1)
sum += b[end].second;
else {
if (left < b[end].second) break;
left -= b[end].second;
sum += b[end].second;
}
end++;
}
ans = max(calc(b, i, end, sum, left), ans);
}
return ans;
}
};

1000. Minimum Cost to Merge Stones

标记难度:Hard

提交次数:1/1

代码效率:32.41%(20ms)

题意

给定N堆石头,每次可以将其中的连续K堆合并为一堆,代价是合并的总石头数。问将这N堆石头合并成一堆的最小代价是多少?

分析

这题面看起来很像是哈夫曼树了,但是要求只能连续合并,所以显然和哈夫曼没什么关系了。

这道题写得我头昏脑涨,总之最后就是看着lee的代码怼出来的,所以也没什么可写题解的,就随便写一下我的感想好了……

  • 看到这种题就是应该DP,虽然DP方程可能会非常复杂。
  • 初始化和转移方程一样,都需要仔细考虑,而且不能瞎考虑。我不知道世界上有没有一种适用于所有DP的思考方法,但估计是没有,所以只能依靠经验了。
  • 这道题的转移顺序比较神奇(大概是区间从小到大……),所以写成递归形式比较好。

每当我觉得我已经学会DP了,就会再次看到一堆我无法把握住的DP题,这说明人要活到老学到老。

代码

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
class Solution {
private:
int f[35][35][35];
int sum[35];
int n, K;

int getSum(int l, int r) {
int x = sum[r];
if (l > 0) x -= sum[l - 1];
return x;
}

int calc(int l, int r, int m) {
if (l > r || m <= 0) return 1e9;
if (f[l][r][m] != -1) return f[l][r][m];
if (l == r) {
if (m == 1) f[l][r][m] = 0;
else f[l][r][m] = 1e9;
return f[l][r][m];
}
if (m == 1) {
f[l][r][m] = calc(l, r, K) + getSum(l, r);
return f[l][r][m];
}
f[l][r][m] = 1e9;
for (int mid = l; mid < r; mid++) {
f[l][r][m] = min(f[l][r][m], calc(l, mid, 1) + calc(mid + 1, r, m - 1));
}
return f[l][r][m];
}

public:
int mergeStones(vector<int>& stones, int K) {
n = stones.size();
for (int i = 0; i < n; i++)
sum[i] = i == 0 ? stones[i] : sum[i - 1] + stones[i];
memset(f, -1, sizeof(f));
this->K = K;
int ans = calc(0, n - 1, 1);
return ans >= 1e9 ? -1 : ans;
}
};

  1. lee215's Solution for 1003 - Python Different Solution

题目来源: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/maximum-width-ramp/description/

标记难度:Medium

提交次数:2/3

代码效率:

  • 排序:124ms
  • 栈:68ms

题意

给定数组A,找到满足i < jA[i] <= A[j](i, j)j - i的最大值。如果没有则返回0。

分析

这道题我的做法是这样的:将数组排序(并记录原来的index),然后遍历数组,记录并不断更新已经出现过的index的最小值,将当前的index[i]减去该最小值即可求出所有可能的(x, i)i - x的最大值。

做的时候因为没有判断好不存在的情况而错了一次。我好像经常因为这种问题犯错。


其实做的时候我隐约感觉到了也许可以用到栈(我之前在Leetcode 84. Largest Rectangle in Histogram)中详细总结了相关内容),但是比赛的时候没仔细思考。

如果需要用到栈,那么不妨把问题化归成这样:对于每个j,找到满足A[i] <= A[j]的最小的i <= j(如果这个i是存在的)。比如说,我们现在有一个A[i],那么它右边的A[i+1], A[i+2], ...如果>= A[i],则它们对结果是毫无意义的,因为我们需要尽量选择靠左的且值比较小的数,A[i]必然会是一个更好的选择。所以可以维护一个值递减的栈(这次不需要弹出了),然后对于每个元素,用二分查找的方式找到最好的candidate,并且在它比栈顶还小的情况下入栈。[1]

很有趣的一点是,之前的问题都是“找到距离最近的元素”,所以直接用栈就可以维护局部性。这次要找到“距离尽量远的元素”,单用栈大概就不够了,需要加上二分查找。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int maxWidthRamp(vector<int>& A) {
// 对于每个数,找到左边比它小的最靠左的数
// 将index排序,找到左边最小的index
vector<pair<int, int>> a;
for (int i = 0; i < A.size(); i++)
a.emplace_back(A[i], i);
sort(a.begin(), a.end());
int N = a.size();
// 我好像经常犯这一类边界条件的错误。
int minn = N + 1, ans = 0;
for (int i = 0; i < N; i++) {
ans = max(ans, a[i].second - minn);
minn = min(minn, a[i].second);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int maxWidthRamp(vector<int>& A) {
vector<pair<int, int>> s;
int ans = 0;
for (int i = 0; i < A.size(); i++) {
if (s.empty() || s.back().first > A[i]) s.emplace_back(A[i], i);
else {
int l = 0, r = s.size();
while (l < r) {
int mid = (l + r) / 2;
if (s[mid].first > A[i])
l = mid + 1;
else
r = mid;
}
if (l < s.size()) ans = max(ans, i - s[l].second);
}
}
return ans;
}
};

  1. lee215's solution for Leetcode 962 - [Java/C++/Python] O(N) Using Stack

题目来源:https://leetcode.com/problems/validate-stack-sequences/description/

标记难度:Medium

提交次数:1/1

代码效率:4ms

题意

给定两个值两两不同的数组(pushedpopped),问它们能否是对一个初始为空的栈进行一系列操作的结果。

分析

一个水题,直接跟着这两个数组模拟就好了,模拟得出来就是可以,模拟不出来就是不行。(简直梦回NOIP普及组笔试题啊……)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int n = pushed.size();
stack<int> s;
int i = 0, j = 0;
while (i < n && j < n) {
while ((s.empty() || s.top() != popped[j]) && i < n)
s.push(pushed[i++]);
if (s.empty()) break;
while (!s.empty() && j < n && s.top() == popped[j]) {
s.pop();
j++;
}
}
return i == n && j == n;
}
};

题目来源:https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/

标记难度:Easy

提交次数:3/3

代码效率:

  • 栈:4ms
  • 计数器:0ms

题意

给定一个只由括号组成的字符串,问如果需要在字符串中添加括号使它变成合法的字符串,最少需要添加多少个括号?

分析

这次比赛的排名是632 / 2700。(人好少。)排名很低的原因一是第三题罚时太多了(靠WA来debug毕竟不可取,还是要好好考虑corner case?),二是这次第四题非常简单,但我却不仅看错了题,暴力也没写对……


这道题很简单,但还稍微有点意思。在何种情况下需要添加括号?如何打印出一种添加括号的方法?

我的第一反应是直接统计左括号和右括号各自的数量,但这么做显然不可取,反例:))((。那么不妨采用我们一般对括号表达式进行思考的方式——栈——来考虑这个问题。在括号入栈的过程中,一个右括号总是和栈中最顶端的还没有配对的左括号配对;如果当前栈中是空的,则这个右括号没有被配对——可以直接在它的左边加上一个左括号;如果最后栈中还剩下一些左括号,则直接在字符串的右侧加上对应数量的右括号。

这个问题也可以简化到不用栈来解决。直接用一个计数器维护当前栈中尚未配对的左括号数量即可。[1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int minAddToMakeValid(string S) {
stack<char> s;
for (char ch: S) {
if (!s.empty() && s.top() == '(' && ch == ')')
s.pop();
else
s.push(ch);
}
return s.size();
}
};

实际地添加括号

写了一个实际添加括号的程序,大概是对的吧。

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
class Solution {
public:
int minAddToMakeValid(string S) {
stack<int> s;
vector<int> toInsBefore;
int ans = 0;
for (int i = 0; i < S.size(); i++) {
if (S[i] == '(')
s.push(i);
else {
if (s.empty()) {
// 记录未配对右括号的位置
toInsBefore.push_back(i);
ans++;
}
else
s.pop();
}
}
for (int i = toInsBefore.size() - 1; i >= 0; i--)
S = S.substr(0, toInsBefore[i]) + '(' + S.substr(toInsBefore[i], S.size() - toInsBefore[i]);
for (int i = 0; i < s.size(); i++) {
ans++;
S += ')';
}
cout << S << endl;
return ans;
}
};

计数器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int minAddToMakeValid(string S) {
int counter = 0, ans = 0;
for (char ch: S) {
if (ch == '(') counter++;
else {
if (counter > 0) counter--;
else ans++;
}
}
return ans + counter;
}
};

  1. rock's solution - [Java] two one pass 7 liners - space O(n) and O(1), respectively

题目来源: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