leetcode 11. Container With Most Water 、42. Trapping Rain Water 、238. Product of Array Except Self

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

上一篇:Caused by: java.lang.IllegalArgumentException: Parameter Maps collection does not contain value for com.bj186.crm.mapper.UserMapper.Integer


下一篇:安卓自定义边栏英文索引控件