柱状图中的最大矩形
$l$数组存储第$i$个数左边第一个小于$i$高度的索引，$r$数组存储第$i$个数右边第一个小于$i$高度的索引；
class Solution {
public:
int largestRectangleArea(vector<int>& heights){
int n = heights.size(),ans = 0;
int l[n],r[n];
l[0] = -1;
r[n - 1] = n;
for(int i = 1;i < n;i++){
if(heights[i] > heights[i - 1]){
l[i] = i - 1;
}else{
int tag = l[i - 1];
while(tag >= 0 && heights[tag] >= heights[i]){
tag = l[tag];
}
l[i] = tag;
}
}
for(int i = n - 2;i >= 0;i--){
if(heights[i] > heights[i + 1]){
r[i] = i + 1;
}else{
int tag = r[i + 1];
while(tag < n && heights[tag] >= heights[i]){
tag = r[tag];
}
r[i] = tag;
}
}
for(int i = 0;i < n;i++){
int s = (r[i] - l[i] - 1) * heights[i];
if(s > ans){
ans = s;
}
}
return ans;
}
};
最大矩形
每层算累计高度然后调用上一问的接口得到结果；
class Solution {
public:
int largestRectangleArea(vector<int>& heights){
int n = heights.size(),ans = 0;
int l[n],r[n];
l[0] = -1;
r[n - 1] = n;
for(int i = 1;i < n;i++){
if(heights[i] > heights[i - 1]){
l[i] = i - 1;
}else{
int tag = l[i - 1];
while(tag >= 0 && heights[tag] >= heights[i]){
tag = l[tag];
}
l[i] = tag;
}
}
for(int i = n - 2;i >= 0;i--){
if(heights[i] > heights[i + 1]){
r[i] = i + 1;
}else{
int tag = r[i + 1];
while(tag < n && heights[tag] >= heights[i]){
tag = r[tag];
}
r[i] = tag;
}
}
for(int i = 0;i < n;i++){
int s = (r[i] - l[i] - 1) * heights[i];
if(s > ans){
ans = s;
}
}
return ans;
}
int maximalRectangle(vector<vector<char>>& matrix) {
vector<int> heights;
int m = matrix.size(),n = matrix[0].size(),ans = 0;
for(int i = 0;i < n;i++){
if(matrix[0][i] == '1'){
heights.push_back(1);
}else{
heights.push_back(0);
}
}
ans = largestRectangleArea(heights);
for(int i = 1;i < m;i++){
for(int j = 0;j < n;j++){
if(matrix[i][j] == '1'){
heights[j] = heights[j] + 1;
}else{
heights[j] = 0;
}
}
int s = largestRectangleArea(heights);
if(s > ans){
ans = s;
}
}
return ans;
}
};
最小覆盖子串
滑动窗口，遍历后记录满足条件的最小窗口；
class Solution {
public:
string minWindow(string s, string t) {
int l = 0,r = 0,tip = t.size();
int ans1 = -1, ans2 = -1, ans = s.size();
int idx[2][26 * 2];
memset(idx, 0, sizeof(idx));
for(int i = 0; i < t.size(); i++){
if(t[i] >= 'A' && t[i] <= 'Z'){
idx[0][int(t[i]) - 65] = 1;
idx[1][int(t[i]) - 65]++;
}else{
idx[0][int(t[i]) - 81] = 1;
idx[1][int(t[i]) - 81]++;
}
}
for(r = 0; r < s.size(); r++){
if(s[r] >= 'A' && s[r] <= 'Z'){
if(idx[0][int(s[r]) - 65] == 1 && idx[1][int(s[r]) - 65] > 0){
tip--;
}
idx[1][int(s[r]) - 65]--;
}else if(s[r] >= 'a' && s[r] <= 'z'){
if(idx[0][int(s[r]) - 81] == 1 && idx[1][int(s[r]) - 81] > 0){
tip--;
}
idx[1][int(s[r]) - 81]--;
}
while(tip == 0 && l <= r){
if(r - l < ans){
ans = r - l;
ans1 = l;
ans2 = r;
}
if(s[l] >= 'A' && s[l] <= 'Z'){
if(idx[0][int(s[l]) - 65] == 1 && idx[1][int(s[l]) - 65] == 0){
tip++;
}
idx[1][int(s[l]) - 65]++;
}else if(s[l] >= 'a' && s[l] <= 'z'){
if(idx[0][int(s[l]) - 81] == 1 && idx[1][int(s[l]) - 81] == 0){
tip++;
}
idx[1][int(s[l]) - 81]++;
}
l++;
if(l > r){
break;
}
}
}
if(ans1 == -1){
return "";
}else{
return s.substr(ans1, ans2 - ans1 + 1);
}
}
};
最长连续序列
直接$sort$比$O(n)$还快，真的无语，思路就是用$unordered$_$set$去重顺便免于排序，然后遍历一遍计算最长连续序列；
class Solution {
public:
unordered_set<int> idx;
int longestConsecutive(vector<int>& nums) {
idx.clear();
int ans = 0;
for(int i = 0;i < nums.size();i++){
idx.insert(nums[i]);
}
for(const int& num : idx){
if(!idx.count(num - 1)){
int now = 1, k = num;
while(idx.count(k + 1)){
k++;
now++;
}
ans = max(now, ans);
}
}
return ans;
}
};
单词拆分
$ans[i]$表示以 i 结尾的字符能否被表示，每次先判断整体能否被表示，然后后向分词判断分别能否被表示；
class Solution {
public:
unordered_map<string, bool> idx;
bool wordBreak(string s, vector<string>& wordDict) {
for(int i = 0;i < wordDict.size();i++){
idx[wordDict[i]] = true;
}
vector<bool> ans(s.size(), false);
for(int i = 0;i < s.size();i++){
if(idx.count(s.substr(0, i + 1)) != 0){
ans[i] = true;
}else{
for(int j = i;j > 0;j--){
if(ans[j - 1] && idx.count(s.substr(j, i - j + 1)) != 0){
ans[i] = true;
break;
}
}
}
}
return ans[s.size() - 1];
}
};
