单调栈
模板
原题
题意：对于数列,中每一个数，输出这个数后面第一个大于它的下标
思路：栈内从大往小放，当栈顶的数小于当前数时，更新栈顶数的answer并弹出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;
using ll = long long;
int n, p = 0;
int a[N], st[N], f[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
for (; p && a[st[p - 1]] < a[i]; --p)
{
f[st[p - 1]] = i;
}
st[p++] = i;
}
for (int i = 1; i <= n; i++)
cout << f[i] << ' ';
return 0;
}
|
经典题：接雨水
原题
一个单调递减的单调栈，能找到每个柱子左边和右边的第一个比它高的柱子，从而计算出可以接住的雨水量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def trap(self, height: List[int]) -> int:
st=[]
ans=0
for r,rh in enumerate(height):
while st and height[st[-1]]<rh:
bottom=st.pop()
if not st:
break
l=st[-1]
w=r-l-1
h=min(height[l],height[r])-height[bottom]
ans+=w*h
st.append(r)
return ans
|
滑动窗口/单调队列
模板
原题
题意：滑动窗口的最小值和最大值
思路：
有更好的新员工，立刻淘汰老员工；
老员工过期了，多好也要淘汰；
新员工永远来到队伍的最底端，队列从头到尾，是从又优秀又老的Top员工，到又普通又新的Back员工。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, k, a[N];
deque<int> maxq, minq;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < k; i++)
{
while (!minq.empty() && minq.front() <= i - k)
minq.pop_front();
while (!minq.empty() && a[minq.back()] >= a[i])
minq.pop_back();
minq.push_back(i);
}
cout << a[minq.front()];
for (int i = k; i < n; i++)
{
while (!minq.empty() && minq.front() <= i - k)
minq.pop_front();
while (!minq.empty() && a[minq.back()] >= a[i])
minq.pop_back();
minq.push_back(i);
cout << ' ' << a[minq.front()];
}
cout << endl;
for (int i = 0; i < k; i++)
{
while (!maxq.empty() && maxq.front() <= i - k)
maxq.pop_front();
while (!maxq.empty() && a[maxq.back()] <= a[i])
maxq.pop_back();
maxq.push_back(i);
}
cout << a[maxq.front()];
for (int i = k; i < n; i++)
{
while (!maxq.empty() && maxq.front() <= i - k)
maxq.pop_front();
while (!maxq.empty() && a[maxq.back()] <= a[i])
maxq.pop_back();
maxq.push_back(i);
cout << ' ' << a[maxq.front()];
}
cout << endl;
return 0;
}
|
经典题：无重复字符的最长子串
原题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
var lengthOfLongestSubstring = function(s) {
const set=new Set();
let j=0,ans=0,n=s.length;
for(i=0;i<n;i++){
while(j<n&&!set.has(s[j])){
set.add(s[j]);
j++;
}
ans=Math.max(ans,j-i);
set.delete(s[i]);
}
return ans;
};
|
https://leetcode.cn/problems/find-all-anagrams-in-a-string?envType=study-plan-v2&envId=top-100-liked
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
| public class Solution {
public IList<int> FindAnagrams(string s, string p) {
var ans=new List<int>();
int sl=s.Length,pl=p.Length;
if(sl<pl){
return ans;
}
int[] cnt=new int[26];
int dif=0;
for(int i=0;i<pl;i++){
++cnt[s[i]-'a'];
--cnt[p[i]-'a'];
}
for(int i=0;i<26;i++){
if(cnt[i]!=0) ++dif;
}
if(dif==0) ans.Add(0);
for(int i=0;i<sl-pl;i++){
int idx=s[i]-'a';
if(cnt[idx]==1) --dif;
else if(cnt[idx]==0) ++dif;
--cnt[idx];
idx=s[i+pl]-'a';
if(cnt[idx]==-1) --dif;
else if(cnt[idx]==0) ++dif;
++cnt[idx];
if(dif==0) ans.Add(i+1);
}
return ans;
}
}
|