11. Container With Most Water
https://www.cnblogs.com/grandyang/p/4455109.html
用双指针向中间滑动,较小的高度就作为当前情况的高度,然后循环找容量的最大值。
不管两个指针中间有多少高度的柱子,只管两头,因为两头的才决定最大容量。
class Solution { public: int maxArea(vector<int>& height) { if(height.empty()) return 0; int res = 0; int begin = 0,end = height.size() - 1; while(begin < end){ int h = min(height[begin],height[end]); res = max(res,(end - begin) * h); h == height[begin] ? begin++ : end --; } return res; } };
42. Trapping Rain Water
https://www.cnblogs.com/grandyang/p/4402392.html
本题与11. Container With Most Water不同,11. Container With Most Water是求两个柱子能装的最多水量,这个题是求的所有柱子能装的水量。
依旧可以使用双指针,一个begin指向第一个柱子,一个end指向最后一个柱子。然后相当于维护一个递减的队列,但又不是完全递减,只是说后面遍历到的应该比这个开始的位置少。一旦出现比这个开始位置大,就要重新更新作为比较的对象。
注意,选择对比的是两个柱子中较短的那根柱子。
class Solution { public: int trap(vector<int>& height) { int begin = 0,end = height.size() - 1; int res = 0; while(begin < end){ int h = min(height[begin],height[end]); if(h == height[begin]){ int tmp = height[begin]; begin++; while(begin < end && height[begin] < tmp){ res += tmp - height[begin]; begin++; } } else{ int tmp = height[end]; end--; while(begin < end && height[end] < tmp){ res += tmp - height[end]; end--; } } } return res; } };
238. Product of Array Except Self
https://www.cnblogs.com/grandyang/p/4650187.html
整体分成左右两个数组进行相乘,这种方式不用两个数组进行存储。
从左向右可以用res[i]就代替前面的乘积,但从右向左就不行了,这个是后res[i]已经是所有的在左侧前方的乘积和,我们还必须计算右侧的乘积和,这个时候用一个变量right来累乘就好了。
其实从左向右也可以用一个变量来累乘。
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { vector<int> res(nums.size(),1); for(int i = 1;i < nums.size();i++){ res[i] = res[i-1] * nums[i-1]; } int right = 1; for(int i = nums.size() - 1;i >= 0;i--){ res[i] *= right; right *= nums[i]; } return res; } };
leetcode 11. Container With Most Water 、42. Trapping Rain Water 、238. Product of Array Except Self