力扣贪心
435. 无重叠区间
先从简单问题开始想：有三个区间，1与2重合，2与3重合，1与3不重合，显然移除2区间即可
也就是说对于已有的两两重合的区间，只需要移除尾部更靠后的区间即可，这样对后面区间的影响比较小
1488. 避免洪水泛滥
比较好想的思路就是，模拟，遇到下雨天ansi=−1ans_i=-1ansi=−1；相反不下雨的一天，只需要抽出当前装满水且之后最先下雨的湖泊
题目终点就转换成了如何找当前装满水且之后最先下雨的湖泊
做法就是从后往前遍历，用map记录某个湖最早出现的位置，不断更新
然后从前往后模拟，每次一个湖装满水，就将其加入优先队列当中
class Solution {
public:struct node{int num,p;bool operator < (const node &x)const{return p>x.p;}};vector<int> avoidFlood(vector<int>& a) {int n=a.size();map<int,int> mp;vector<int> pos(n);for (int i=n-1;i>=0;i--){if (!mp[a[i]]){pos[i]=n+1;mp[a[i]]=i;}else{pos[i]=mp[a[i]];mp[a[i]]=i;}}vector<int> b;map<int,bool> vis;priority_queue<node> q;for (int i=0;i<n;i++){if (a[i]){if (vis[a[i]]){b.clear();return b;}else{vis[a[i]]=1;q.push({a[i],pos[i]});}b.push_back(-1);}else{if (!q.empty()){node x=q.top();q.pop();vis[x.num]=0;b.push_back(x.num); }else{b.push_back(1);}}}return b;}
};
312. 戳气球
区间dp
先求子区间的最优答案，然后推出整个区间的最优答案
设dpi,jdp_{i,j}dpi,j为区间[i,j][i,j][i,j]内气球全戳爆的最大得分，
转移方程就是dpi,j=max(dpi,k−1+dpk+1,j+ak∗ai−1∗aj+1)dp_{i,j}=max(dp_{i,k-1}+dp_{k+1,j}+a_k*a_{i-1}*a_{j+1})dpi,j=max(dpi,k−1+dpk+1,j+ak∗ai−1∗aj+1)
5. 最长回文子串
首先考虑回文子串的定义，然后得到回文子串除去首尾，内部一定是一个回文子串，那么可以用区间dp来将较小区间的回文子串拓展到更大区间的回文子串
dpi,j=1dp_{i,j}=1dpi,j=1 需满足条件ai==aja_i==a_jai==aj && dpi+1,j−1=1dp_{i+1,j-1}=1dpi+1,j−1=1，如果一个区间[i,j]，ai!=aj[i,j]，a_i!=a_j[i,j]，ai!=aj，这个区间一定不是回文子串即dpi,j=0dp_{i,j}=0dpi,j=0
注意初始化对于长度为1的区间一定是回文子串
长度为2且两个字符相等的区间也是回文子串
最后找到最长的dp=1的区间即可
11. 盛最多水的容器
对于一个区间[i,j][i,j][i,j]，其面积为min(hi,hj)∗(j−i+1)min(h_i,h_j)*(j-i+1)min(hi,hj)∗(j−i+1)，于是有以下贪心：
设hi<hjh_i<h_jhi<hj，那么如果将jjj向左移至j−1j-1j−1，min(hi,hj−1)<=min(hi,hj)min(h_i,h_{j-1})<=min(h_i,h_j)min(hi,hj−1)<=min(hi,hj)，而宽度由j−i+1j-i+1j−i+1变为j−ij-ij−i，所以此时的面积一定比之前小
如果将iii向左移至i+1i+1i+1，min(hi+1,hj)与min(hi,hj)min(h_{i+1},h_j)与min(h_i,h_j)min(hi+1,hj)与min(hi,hj)的关系是不确定的，可能出现hi+1>hih_{i+1}>h_ihi+1>hi的情况，最终导致变化后面积更大
于是有以下贪心：先求出最大区间的面积，然后不断将两端高度最小的那一端向内移动，更新答案