之前博客介绍了采用双指针法来解决链表类题目Link。 本博文主要介绍用双指针法来解决数组类题目，并且把数组类相关的解题思路也放在此博客中。
数组与链表是最基本的两种数据结构，其他均可以由这两种构成。 链表是用离散的内存块存储数据，而数组是用连续的内存块存储数据。 因此，对于数组，只需要直知道内存空间首地址（也就是数组名），通过索引即可访问任意元素。
在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。
- 左右指针: 两个指针相向而行或者相背而行。
- 快慢指针：两个指针同向而行，一快一慢。
虽然在数组中并没有真正意义上的指针，但可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧，
// C++ 中的vector的使用
// 不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容
vector<int> arr;
for (int i = 0; i < 10; i++) {
// 在末尾追加元素，时间复杂度 O(1)
arr.push_back(i);
}
// 在中间插入元素，时间复杂度 O(N)
// 在索引 2 的位置插入元素 666
arr.insert(arr.begin() + 2, 666);
// 在头部插入元素，时间复杂度 O(N)
arr.insert(arr.begin(), -1);
// 删除末尾元素，时间复杂度 O(1)
arr.pop_back();
// 删除中间元素，时间复杂度 O(N)
// 删除索引 2 的元素
⚠️！注意使用方式
arr.erase(arr.begin() + 2);
// 根据索引查询元素，时间复杂度 O(1)
int a = arr[0];
// 根据索引修改元素，时间复杂度 O(1)
arr[0] = 100;
// 根据元素值查找索引，时间复杂度 O(N)
int index = find(arr.begin(), arr.end(), 666) - arr.begin();
//交换两个index的元素
swap(arr[i], arr[j]);
//求index i到j之间的最大值
int max = *max_element(arr.begin() + i, arr.begin() + j + 1);
//求index i到j之间的最小值
int min = *min_element(arr.begin() + i, arr.begin() + j + 1);
1. 删除有序数组中的重复项
第一次遇到这个题目的时候，还是比较困惑的，主要是返回什么。题目要求是“原地修改”。如果不是原地修改的话，我们直接 new 一个 int[] 数组，把去重之后的元素放进这个新数组中，然后返回这个新数组即可。 而所谓的“原地修改”，其实就是原地删除，不允许 new 新数组，只能在原数组上操作，然后返回一个长度，这样就可以通过返回的长度在原始数组中截取去重后的元素了。
对于此代码，原本有两个解法：
解法1：采用unique函数。时间复杂度O(Nlogn)，空间复杂度为O（1）
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
sort(nums.begin(),nums.end());
// 解法1:时间复杂度O(Nlogn)，空间复杂度为O（1）
// 采用unique来“去除”容器或者数组中相邻元素的重复出现的元素
auto iter=unique(nums.begin(),nums.end());//返回一个指向去重后序列末尾的迭代器。
// unique 并不会改变容器的大小，只是将不重复的元素移到前面，返回去重后末尾的迭代器（最后一个不重复元素）
// 去重过程：不停的把后面不重复的元素移到前面来，也可以说是用不重复的元素占领重复元素的位置。
return iter-nums.begin();//这就是不重复的元素的个数
}
};
解法2：采用键值对,时间复杂度为O（n），由于需要一个键值对，空间复杂度估计也是O（n）
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
// 解法2：采用键值对,时间复杂度为O（n）
map<int,int> group;//会自动根据键的大小进行排序，而输入的数组本身就是递增的。所以可以使用
for(int i=0;i<nums.size();i++)
{
group[nums[i]]++;
}
nums.clear();//清空，需要重新放入，用于验证
for(auto value:group)//遍历map中的每个对
{
nums.push_back(value.first);//获取键
}
return nums.size();
}
};
而快慢指针法的思路就是：慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。
这样，就保证了 nums[初始点..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[初始点..slow] 就是整个数组去重之后的结果。
时间复杂度为O（n），空间复杂度为O（1）
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
//采用双指针法（快慢指针）时间复杂度为O（n），空间复杂度为O（1）
int slow=0, fast=0;
while(fast!=nums.size())//遍历整个数组
{
if(nums[slow]!=nums[fast])//找到不等的
{
slow++;//slow自增（必须先自增，因为一开始fast=slow，下一刻再判断时必须要先把slow自增）
nums[slow]=nums[fast];//进行赋值
}
fast++;
}
//代码将不重复的元素放在数组前面slow索引中～
return slow+1;//这个就是排在前面的不重复的size（注意要+1）
}
};
对于前面的解法1和解法2，特别是解法1，除非比较熟悉cpp的函数，不然一般不懂使用，所以更建议实际解题的时候用算法去解题而不是用库函数取巧🤭 而类似的题目链表类博客中有记录了，给出了两个解法（见Leetcode中83题）
2.移除元素（原地删除而非上面的换位置）
解法1：数组函数的使用，时间复杂度O(Nlogn+N)；空间复杂度O（1）
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
// 先进行排序,排序后只需要对找到对应值的位置进行删除即可
sort(nums.begin(),nums.end());//时间复杂度为O（nlogn）
auto index=find(nums.begin(),nums.end(),val);//返回的是指针（时间复杂度为O（n））
if(index!=nums.end())//代表找到了
{
//从找到的位置开始，到结尾
for(auto it=index;it!=nums.end();)
{
if(*it==val)
{
it = nums.erase(it);//直接删掉
}
else
break;
}
}
return nums.size();//返回的是nums 中与 val 不同的元素的数量
}
};
解法2：快慢指针，其实跟上面题1的思路是一样的。时间复杂度为O（n），空间复杂度为O（1）
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow=0, fast=0;
while(fast!=nums.size())
{
if(nums[fast]!=val)//不等
{
nums[slow]=nums[fast];
slow++;
}
fast++;
}
return slow;
//此处与有序数组去重的解法有一个细节差异：
// 先给 nums[slow] 赋值然后再slow++
// nums[0..slow-1] 是不包含值为 val 的元素的，最后的结果数组长度就是 slow
}
};
3.移动零
类似上面的解法，只是改为vector以及没有返回值。时间复杂度为O（n），空间复杂度为O（1）
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 快慢指针
int slow=0,fast=0;
while(fast!=nums.size())
{
if(nums[fast]!=0)//若不为零
{
nums[slow]=nums[fast];
slow++;
}
fast++;
}
while(slow!=nums.size())
{//由于没有返回值，把后面的也赋值为0（因为可能是原本位置的其他值，上面并不是交换操作）
nums[slow]=0;
slow++;
}
}
};
4. 两数之和
左右指针,时间复杂度应该为O（N），空间复杂度应该为O（1）
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
// 由于数组已经按照非递减顺序排序，故此可以用左右指针法
int left=0, right=numbers.size()-1;
while(left<right)
{
int sum=numbers[left]+numbers[right];
if(sum==target)//找到了
{
return vector<int>{left+1, right+1};//索引从1开始
}
else if(sum<target)
{
left++;//让值大一些
}
else if(sum>target)
{
right--;//让值小一些
}
}
return vector<int>{ -1, -1};//找不到
}
};
用hash table (时间复杂度为O（N）)
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int value_a,value_b;
vector<int> result;
// 用hash table (时间复杂度可以降为O（N）)
unordered_map<int, int> hash_able;//(具体的值、坐标)
for(int i=0;i<numbers.size();i++)
{
auto it=hash_able.find(target-numbers[i]);//寻找这个值的另一半
// 如果找到了，
if(it!=hash_able.end())
{
int index_1=it->second;
int index_2=i;
// 注意返回的为坐标值（且下标开始为1）
result.push_back(index_1+1);
result.push_back(index_2+1);
break;
}
hash_able[numbers[i]]=i;//若没找到，就继续放入hash table
}
return result;
}
};
相类似的题目还有下题（几乎一样，只是下标索引从1开始）：
解法1：用hash table (时间复杂度为O（N）)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int value_a,value_b;
vector<int> result;
// 用hash table (时间复杂度可以降为O（N）)
unordered_map<int, int> hash_able;//(具体的值、坐标)
for(int i=0;i<nums.size();i++)
{
auto it=hash_able.find(target-nums[i]);//寻找这个值的另一半
// 如果找到了，
if(it!=hash_able.end())
{
int index_1=it->second;
int index_2=i;
// 注意返回的为坐标值
result.push_back(index_1);
result.push_back(index_2);
break;
}
hash_able[nums[i]]=i;//若没找到，就继续放入hash table
}
return result;
}
};
解法2： 暴力匹配的解法（时间复杂度为O（N^2））这必然非最优解了🤭
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int value_a,value_b;
vector<int> result;
// 暴力匹配的解法（时间复杂度为O（N^2））
for(int i=0;i<nums.size();i++)
{
value_a=nums[i];
for(int j=i+1;j<nums.size();j++)
{
value_b=nums[j];
if(value_a+value_b==target)
{
result.push_back(i);
result.push_back(j);
break;
}
}
}
return result;
}
};
5.反转数组
最简单的就是采用reverse函数了~时间复杂度O(n)
class Solution {
public:
void reverseString(vector<char>& s) {
//采用reverse函数
reverse(s.begin(),s.end());
}
};
但是还是采用双指针法来看看,时间复杂度O(n),空间复杂度为O（1）跟上面一样
class Solution {
public:
void reverseString(vector<char>& s) {
int left=0, right=s.size()-1;
while(left<right)//等于的时候不处理了
{
char temp=s[left];//用个中间变量来赋值~
s[left]=s[right];
s[right]=temp;
left++;
right--;
}
}
};
6.最长回文子串
回文子串的判断应该是经典的动态规划的题目，但是复杂度是O（N^2）。空间复杂度是O（N^2）（存储动态规划状态需要的空间。）
class Solution {
public:
string longestPalindrome(string s) {
int max_length=1;//最长的长度
int begin_index=0;//起始的index
// 动态规划
// 对于坐标为i~j的子串，是否回文子串，状态为dp[i][j]
bool dp[s.size()][s.size()]; //定义动态规划的状态矩阵大小
//确定初始状态，所有长度为1的都是回文子串
for(int i=0;i<s.size();i++)
{
int j=i;
dp[i][j]=true;
}
//进行递推状态转移
// for(int i=0;i<s.size();i++)
for(int i=s.size()-1;i>=0;i--)//要从小到大！！！
{
for(int j=i+1;j<s.size();j++)//j=i的情况以及是初始化了
{
if(s[i]==s[j])//如果相等，那么就检查下一个状态
{
if(j<=i+2)//如果此时到达边界（aba）或（aa）的情况
dp[i][j]=true;
else//继续递推
dp[i][j]=dp[i+1][j-1];
}
else//如果不等，那么当前就是false
dp[i][j]=false;
//如果是回文子串且长度大于记录值
if(dp[i][j] && j-i+1>max_length)
{
begin_index=i;
max_length=j-i+1;
}
}
}
return s.substr(begin_index,max_length);//字符串的截取
}
};
采用双指针解法,时间复杂度是O（N^2）更上面一样的。但空间复杂度更小，为O（1）
class Solution {
public:
// 对于以left与right为中心的最长回文子串
// 通过左右指针向两边扩散
string function(string s, int left, int right)
{
//确保不越界以及相等
while(left>=0 && right<s.size() &&s[left]==s[right])
{
left--;
right++;
}
//若不等的话，会跳出来。所以应该是当前的left+1到right为目标结果
return s.substr(left+1,right-(left+1));
}
string longestPalindrome(string s) {
string result="";
for(int i=0;i<s.size();i++)
{
//以i为中心的，奇数字符串
string s1=function(s,i,i);
//以i为中心的，偶数字符串
string s2=function(s,i,i+1);
// 保存最长的
result= result.size()>s1.size()? result:s1;
result= result.size()>s2.size()? result:s2;
}
return result;
}
};
下面是几乎一样的题目
先给出双指针解法，跟上面几乎一样～
#include <iostream>
using namespace std;
// 对于以left与right为中心的最长回文子串
// 通过左右指针向两边扩散
string function(string s, int left, int right)
{
//确保不越界以及相等
while(left>=0 && right<s.size() &&s[left]==s[right])
{
left--;
right++;
}
//若不等的话，会跳出来。所以应该是当前的left+1到right为目标结果
return s.substr(left+1,right-(left+1));
}
int main() {
//本质上就是求最长的回文子串。可以采用动态规划或者双指针法
string input_str, result_str;
getline(cin,input_str);
for(int i=0;i<input_str.size();i++)
{
//以i为中心的，奇数字符串
string s1=function(input_str,i,i);
//以i为中心的，偶数字符串
string s2=function(input_str,i,i+1);
// 保存最长的
result_str= result_str.size()>s1.size()? result_str:s1;
result_str= result_str.size()>s2.size()? result_str:s2;
}
std::cout<<result_str.size();
}
下面是动态规划的解法，还是双指针法比较简单，建议实际用双指针法解决～
#include <iostream>
#include <vector>
using namespace std;
int main() {
//本质上就是求最长的回文子串。可以采用动态规划或者双指针法
string input_str, result_str;
getline(cin,input_str);
//step1:定义dp表，对于起点为i终点为j的dp[i][j]是否为回文串
// i，j为字符的索引
vector< vector <bool> > dp(input_str.size(), vector<bool> (input_str.size(),false));
//step2:初始化dp表：当i=j的时候，回文子串为自身，也就是true
// for(int i=0;i<input_str.size();i++)
// {
// for(int j=0;j<input_str.size();j++)
// {
// if(i==j)
// dp[i][j]=true;
// }
// }
for(int i=0;i<input_str.size();i++)
{
int j=i; //自身都是回文子串
dp[i][j]=true;
}
int max_len=0;
// step3:状态转移方程
for(int i=input_str.size()-1;i>=0;i--)//从右往左
{
for(int j=i+1;j<input_str.size();j++)//从左往右
{
if(input_str[i]==input_str[j])//若相等，就检查下一个状态
{
if(j<=i+2)//如果此时到达边界（aba）或（aa）的情况
dp[i][j]=true;
else//否则就继续缩小范围
dp[i][j]=dp[i+1][j-1];//往内缩小
}
else//若不等，那么就不是回文子串
dp[i][j]=false;
if(dp[i][j]==true)//若当前为回文子串
{
if(j-i+1>max_len)
max_len=j-i+1;//如果是回文子串且长度大于记录值,则更新
}
}
}
std::cout<<max_len<<std::endl;
}
下面的动态规划解法更容易理解些～
#include <iostream>
#include <vector>
using namespace std;
int main() {
//本质上就是求最长的回文子串。可以采用动态规划或者双指针法
string input_str, result_str;
getline(cin,input_str);
//step1:定义dp表，对于起点为j终点为i的dp[j][i]是否为回文串
// i，j为字符的索引
//step2:初始化dp表：全部为false
vector< vector <bool> > dp(input_str.size(), vector<bool> (input_str.size(),false));
int max_len=0;
// step3:状态转移方程
for(int i=0;i<input_str.size();i++)
{
for(int j=0;j<=i;j++)
{
if(i==j)//自身必然为回文子串。//对应aba的情况，基数位
dp[j][i]=true;//注意是j～i
else if(i==j+1)//对应偶数位，回文子串
{
dp[j][i]=(input_str[i]==input_str[j]);
}
else//其他情况
dp[j][i]= (input_str[i]==input_str[j]) && dp[j+1][i-1];//从小范围到大范围
if(dp[j][i]==true)//若当前为回文子串
{
if(i-j+1>max_len)
max_len=i-j+1;//如果是回文子串且长度大于记录值,则更新
}
}
}
std::cout<<max_len<<std::endl;
}
采用二分法来解数组类题目
二分法其实就是左右双指针法的一种特殊情况，即两个指针分别指向数组的两端，然后根据题目的要求，每次将指针移动到中间，然后根据中间的值来判断下一步应该移动哪个指针。 更多关于二分法的介绍请见博客Link。
采用滑动窗口算法来解数组类题目
调滑动窗口算法的快慢指针特性：left 指针在后，right 指针在前，两个指针中间的部分就是「窗口」，算法通过扩大和缩小「窗口」来解决某些问题。 更多关于滑动窗口算法的介绍请见博客Link。
三数之和
先确定一个值，另外两个通过左右指针的方式获取
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());// 先对数组进行排序（这样可以避免用到重复的结果）
for(int index=0; index<nums.size();index++)//规定起点为index
{
//由于前面进行了排序，因此这样可以避免重复的结果
if (index > 0 && nums[index] == nums[index - 1]) //一样的话，情况一样，但是输出要求顺序不重要！
continue; // Skip duplicate elements
int target_value=-nums[index];//获下面两数之和的目标值
// 采用左右指针
int right=nums.size()-1;
int left=index+1;
while(left<right)
{
if(nums[left]+nums[right]>target_value)
{
right--;
}
else if(nums[left]+nums[right]<target_value)
{
left++;
}
else//相同
{
// vector<int> temp={nums[index],nums[left],nums[right]};
result.push_back({nums[index],nums[left],nums[right]});
//然后继续移动指针避免重复的答案
while (left < right && nums[left] == nums[left + 1])
left++;
while (left < right && nums[right] == nums[right - 1])
right--;
//必须要继续移动，不然会报错爆内存。要么break掉，但是break掉导致不全
left++;
right--;
}
}
}
return result;
}
};
解法2也是双指针
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());// 先对数组进行排序（这样可以避免用到重复的结果）
for(int index=0; index<nums.size();index++)//规定起点为index
{
//由于前面进行了排序，因此这样可以避免重复的结果
if (index > 0 && nums[index] == nums[index - 1]) //一样的话，情况一样，但是输出要求顺序不重要！
continue; // Skip duplicate elements
int target_value=-nums[index];//获下面两数之和的目标值
// 解法1：采用左右指针
int right=nums.size()-1;
for(int left=index+1;left<nums.size();left++)
{
//由于前面进行了排序，因此这样可以避免重复的结果
if (left > index+1 && nums[left] == nums[left - 1])
continue; // Skip duplicate elements
while(left<right && nums[left]+nums[right]>target_value)
right--; // 每次都要遍历,按顺序排列，如果值大了还可以减
if(right<=left)//交叉了
break;
if(nums[left]+nums[right]==target_value)//找到了
result.push_back({nums[index],nums[left],nums[right]});
}
// //解法2 下面做法跟两数之和类似，但是会超出时间限制308 / 313 个通过的测试用例
// unordered_map<int, int> hash_table;
// for(int i=index+1;i<nums.size();i++)
// {
// auto it=hash_table.find(target_value-nums[i]);
// if(it!=hash_table.end())//找到了
// {
// vector<int> temp={nums[index], nums[i], it->first};
// // if(find(result.begin(),result.end(),temp)==result.end())//避免重复
// result.push_back(temp);
// }
// hash_table[nums[i]]=i;
// }
}
// Remove duplicates from result（对最后的结果来去重，这可以满足计算量要求，但是不比双指针好）
// result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
};
最接近的三数之和
有时做最大最小值记录的时候，可以选择初始化为INT_MIN和INT_MAX
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
// 以一个很大的值为初始值
int min_diff=INT_MAX;//记录为离target差多少。为0的时候就是target
int closest_sum;//最近的结果
//先进行排序，这样双指针解法才好做
sort(nums.begin(),nums.end());
for(int index=0;index<nums.size();index++)
{
// if(index>0 && nums[index]=nums[index-1])//这种情况是否重复呢？如果是求最值应该不存在重复的情况
// continue;
int target_value=target-nums[index];
int left=index+1;
int right=nums.size()-1;
while(left<right)
{
int current_sum = nums[index] + nums[left] + nums[right];
int current_diff = abs(current_sum - target);
//更新当前的最小值
if (current_diff < min_diff) {
min_diff = current_diff;
closest_sum = current_sum;
}
if(nums[left]+nums[right]<target_value)
{
left++;
}
else if(nums[left]+nums[right]>target_value)
{
right--;
}
else//相等的情况
{
return target;
}
}
}
return closest_sum;
}
};
四数之和
最直接的方法就是用回溯算法。但是运行会超时。230 / 294 个通过的测试用例
class Solution {
public:
void backtrack(vector<int>& nums, int target,vector<int> each_path,vector<vector<int>>& results, int index)
{
//递归终止的条件
if(each_path.size()==4)
{
if(target==0)//刚好为0
results.push_back(each_path);
return;
}
//选择列表
for(int i=index;i<nums.size();i++)
{
// 满足条件进行剪枝,以此去重
if(i>index && nums[i]==nums[i-1])//若当前值等于上一个值.同时除掉最开始的index以保证每次选重复值的第一个
continue;
// if(target-nums[i]<0)//剪枝(由于target存在负数，不能用此剪枝)
// continue;
//前序做选择
each_path.push_back(nums[i]);
backtrack(nums,target-nums[i],each_path,results,i+1);
//后序撤销选择
each_path.pop_back();
}
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
//由于要求按顺序返回，故此先排序
sort(nums.begin(),nums.end());
//其次返回所有的可能，因此用回溯算法解题应该是最直接的
vector<vector<int>> results;
vector<int> each_path;
backtrack(nums,target,each_path,results,0);
return results;
}
};
要避免超时应该采用的是双指针法，类似三数之和。在三数和的基础上上再套一层for循环.注意测试样例中存在long数据。时间复杂度为O（N3）
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());// 先对数组进行排序（这样可以避免用到重复的结果，同时题目要求的也是从小到大返回）
for(int index_1=0;index_1<nums.size();index_1++)
{
//由于前面进行了排序，因此这样可以避免重复的结果
if (index_1 > 0 && nums[index_1] == nums[index_1 - 1]) //一样的话，情况一样
continue; // Skip duplicate elements
for(int index_2=index_1+1;index_2<nums.size();index_2++)
{
//类似上面的剪枝
if (index_2 > index_1+1 && nums[index_2] == nums[index_2 - 1]) //一样的话，情况一样
continue; // Skip duplicate elements
// int target_value= target-nums[index_1]-nums[index_2];
long target_value= target- (long) (nums[index_1]+nums[index_2]);//测试样例中存在long
//左右指针法
int left=index_2+1;//第三个
int right=nums.size()-1;//第四个
while(left<right)
{
if(nums[left]+nums[right]>target_value)
{
right--;
}
else if(nums[left]+nums[right]<target_value)
{
left++;
}
else //相同
{
// 记录结果
result.push_back({nums[index_1],nums[index_2],nums[left],nums[right]});
//然后继续移动指针避免重复的答案
while (left < right && nums[left] == nums[left + 1])
left++;
while (left < right && nums[right] == nums[right - 1])
right--;
//必须要继续移动，不然会报错爆内存。要么break掉，但是break掉导致不全
left++;
right--;
}
}
}
}
return result;
}
};
高效解决接雨水问题
接雨水
首先给出暴力的解法。这个思路是最直接的，把问题进行分解然后解题，但是最终只有320 / 323 个通过的测试用例 时间复杂度应该是O（N2）
class Solution {
public:
int trap(vector<int>& height) {
// 实际上就是用一个数组表示一个条形图，问这个条形图最多能接多少水
// 简化题目：对于位置i，它的左边和右边最大的柱子高度为：l_max, r_max。而装水的容量为min(l_max, r_max)-height[i] （对应一格）
// 而l_max=max(height[0..i])
// r_max=max(height[i..end])
//
int result=0;
for(int i=0;i<height.size();i++)
{
int left_max = *max_element(height.begin() , height.begin() + i);
int right_max = *max_element(height.begin()+i, height.end());
if(min(left_max,right_max)-height[i]>=0)//要大于0才加，小于0为负就是没有水
result+=min(left_max,right_max)-height[i];
}
return result;
}
};
通过备忘录，先预先计算每个i的两个数组，避免每次循环都重复遍历，可以将时间复杂度降低为O(N),空间复杂度为O（1）
class Solution {
public:
int trap(vector<int>& height) {
vector<int> left_max(height.size(),0);
left_max[0]=height[0];//初始化
for(int i=1;i<height.size();i++)
{
left_max[i]=max(height[i],left_max[i-1]);
}
vector<int> right_max(height.size(),0);
right_max[height.size()-1]=height[height.size()-1];//初始化
// 注意：此处需要从右到左遍历
for(int i=height.size()-2;i>=0;i--)
{
right_max[i]=max(height[i],right_max[i+1]);
}
int result=0;
for(int i=0;i<height.size();i++)
{
if(min(left_max[i],right_max[i])-height[i]>=0)//要大于0才加，小于0为负就是没有水
result+=min(left_max[i],right_max[i])-height[i];
}
return result;
}
};
下面通过双指针法解题，将时间复杂度一样为O（N），如下图所示
class Solution {
public:
int trap(vector<int>& height) {
int result=0;
int left_max=0, right_max=0;//相当于数组
int left_index=0, right_index=height.size()-1;
while(left_index<right_index)
{
left_max=max(left_max,height[left_index]);
right_max=max(right_max,height[right_index]);
//result+=min(left_max,right_max)-height[i]
// 只在乎 min(l_max, r_max)。
// 当已经知道 l_max < r_max 了，这个 r_max 是不是右边最大的，不重要。
// 重要的是 height[i] 能够装的水只和较低的 l_max 之差有关：
if(left_max<right_max)//result就由此处的left决定
{
result+=left_max-height[left_index];
left_index++;
}
else
{
result+=right_max-height[right_index];
right_index--;
}
}
return result;
}
};
盛最多水的容器
上一题给出的类似一幅直方图，每个横坐标都有宽度，而本题给出的每个横坐标是一条竖线，没有宽度。因此就不存在height[i]存放多少水的问题。
因此本题只需要知道了两个指针的位置，就可以计算出最大的面积：min(height[left], height[right]) * (right - left)
class Solution {
public:
int maxArea(vector<int>& height) {
int result=0;
int left_index=0, right_index=height.size()-1;
while(left_index<right_index)
{
// [left, right] 之间的矩形面积
int cur_value = min(height[left_index], height[right_index]) * (right_index - left_index);
result=max(result,cur_value);
// 因为矩形的高度是由 min(height[left], height[right]) 即较低的一边决定的
// 如果移动较低的那一边，那条边可能会变高，使得矩形的高度变大，进而就「有可能」使得矩形的面积变大；
// 相反，如果移动较高的那一边，矩形的高度是无论如何都不会变大的，所以不可能使矩形的面积变得更大。
if(height[left_index]<height[right_index])
{
left_index++;
}
else
{
right_index--;
}
}
return result;
}
};
下面写法是一样的。注意更新的索引不要写错了～
class Solution {
public:
int maxArea(vector<int>& height) {
int result=0;
int left_index=0, right_index=height.size()-1;
while(left_index<right_index)
{
if(height[left_index]<height[right_index])
{
int cur_value=height[left_index]*(right_index-left_index);
result=max(result,cur_value);
left_index++;
}
else
{
int cur_value=height[right_index]*(right_index-left_index);
result=max(result,cur_value);
right_index--;
}
}
return result;
}
};