子串
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
代码参考《代码随想录》
class Solution {
private:
//思路：假如存在一种可以实现 pop() push() 和 getMax() 功能的队列，再用该队列遍历原数组，每次步进均获取并存储一次最大值，即可获取滑动窗口最大值
//需求：每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.front()就返回我们要的最大值。
//现状：没有现成的这种队列，但是可以考虑自己造，将其命名为单调队列
//底层数据结构：deque 双端队列，两头可进出，第一个元素称为 front，最后一个元素称为 back
//规定：为了方便获取最值，应该将最值放在 front 或 end 的位置，此处将最大值放在 front 的位置（此处体现结构决定功能的思维，用结构实现功能，而非功能适应于结构）
//结构优先，等效实现：必须保证队列内部元素的有效性，可以只维护必要信息，如此处的 pop 和 push，不一定就要将元素加入 deque 中，只在特定情况下操作即可
//理念：在单调队列中维护可能成为最大值的元素
//此处的滑动窗口并不等同于单调队列，从执行流程上来看是滑动窗口（逻辑结构），从具体实现上来看是单调队列（物理结构）
// pop(int value)：表示在滑动窗口中移出元素
// push(int value)：表示在滑动窗口中移入元素
// getMax()：获取最大值
class MyQueue { //单调队列：维护从大到小的元素信息
public:
deque<int> que; // 使用deque来实现单调队列
// pop的逻辑功能：当滑动窗口移动时，在滑动窗口中移出元素
// 关键点：要保证单调队列内部元素的有序性 → 暗含前提：单调队列内部元素本身就是有序的
// pop的具体实现：
// 因为队列内部元素从大到小，所以
// 1.如果要移出的元素是滑动窗口中最大的元素，需要在单调队列中弹出表示最大元素的 front
// 2.如果要移出的元素不是滑动窗口中最大的元素，什么也不用做（因为单调队列中最大元素不变）
// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。此时代表着先前的最大元素已经被移出滑动窗口
// 同时pop之前判断队列当前是否为空。
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
// push的逻辑功能：当滑动窗口移动时，在滑动窗口中移入元素
// push的具体实现：
// 关键点：要保证单调队列内部元素的有序性 → 暗含前提：单调队列内部元素本身就是有序的
// 因为队列内部元素从大到小，所以将小于要push的元素不断从back弹出，再将要push的元素从back插入即可
// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
int front() {
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> result;
// 用滑动窗口处理前k元素
for (int i = 0; i < k; i++) {
que.push(nums[i]);
}
result.push_back(que.front()); // result 记录前k的元素的最大值
// 滑动窗口开始滑动
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i - k]); // 滑动窗口移除最前面元素
que.push(nums[i]); // 滑动窗口前加入最后面的元素
result.push_back(que.front()); // 记录对应的最大值
}
return result;
}
};
76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
代码参考《labuladong 的算法小抄》
class Solution {
public:
string minWindow(string s, string t) {
string res;
//需要满足字符数量的字母，滑动窗口
unordered_map<char, int> need, window;
for(char c : t) need[c]++;
//快慢指针
int left = 0, right = 0;
//符合要求的字母数量
int valid = 0;
//字符串的等效表示方法
int start = 0, len = INT_MAX;
//快指针越界控制
while(right < s.size()){
//获取要移入的字符
char in = s[right];
//移入信号
right++;
//只在需要时处理
if(need.count(in)){
//移入执行，移入执行后处理 valid
window[in]++;
//滑动窗口中字母拥有的字符数量 == 字母所需的字符数量，符合要求的字母数量++
if(window[in] == need[in]){
valid++;
}
}
//需要满足要求的字母数量 == 符合要求的字母数量
while(need.size() == valid){
//更新最小覆盖子串
if(need.size() == valid){
if(right - left < len){
start = left;
len = right - left;
}
}
//获取要移出的字符
char out = s[left];
//移出信号
left++;
//只在需要时处理
if(need.count(out)){
//移出前滑动窗口中字母拥有的字符数量 == 字母所需的字符数量
//则移出后符合要求的字母数量--
if(window[out] == need[out]){
valid--;
}
//移出执行，处理 valid 后执行移出
window[out]--;
}
}
}
//结果获取
res = (len == INT_MAX ? "" : s.substr(start, len));
return res;
}
};
普通数组
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
回顾：动规五部曲
- 定义
- 定式
- 定初值
- 定序
定中值
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//一维dp
//定义：源于题目,以 i 结尾最大子数组和
//定式：dp[i] = max(dp[i - 1] + nums[i], nums[i])
//定初值：dp[0] = nums[0]
//定序：从左到右遍历
//dp[i]: i 结尾 连续子数组最大和
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
// 要求取最值，且可能存在负数，故不能取 0
int res = INT_MIN;
for(int i = 1; i< nums.size(); i++){
dp[i] = max(dp[i-1]+nums[i], nums[i]);
if (dp[i] > res) res = dp[i];
}
// 下标 0 与 res 的比较会漏掉，此处补回来
if(dp[0] > res) res = dp[0];
return res;
}
};
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
//剪枝：空集直接返回空集
if(intervals.empty()) return {};
//排序
sort(intervals.begin(), intervals.end(),compare);
res.push_back(intervals[0]);//将第一个区间放入 res
for(int i = 0; i < intervals.size(); i++){
//intervals[i] 的 start < res最后一个元素的 end，合并
if(intervals[i][0] <= res.back()[1]){
//更新最后一个区间的结束位置
res.back()[1] = max(intervals[i][1], res.back()[1]);
}else{
res.push_back(intervals[i]);
}
}
return res;
}
};
189. 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105
class Solution {
public:
void rotate(vector<int>& nums, int k) {
//纯粹技巧
int n = nums.size();
//取模，去周期
k = k%n;
//翻转全部元素
reverse(nums.begin(), nums.end());
//翻转前 k 个元素
reverse(nums.begin(), nums.begin()+k);
//翻转后 nums.size() - k 个元素
reverse(nums.begin()+k, nums.end());
}
};