Leetcode每天兩題6-第11題和第42題

剛回北京好累啊，又要上班不開心！！

開始更新。

11. Container With Most Water

給定n個非負數整數a1, a2, ..., an, 每個數代表坐標(i, ai)的一個點。以(i, ai) 和 (i, 0)為線段的端點畫了n條垂直的線。 找到其中兩條， 使他們和x軸形成的一個容器可以裝最多的水。

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

代碼+注釋

class Solution {public:int maxArea(vector<int>& height) {//先以最外層兩個數據為初始面積，並建立左右兩個索引//移動左右兩個索引使面積更大//左邊 大於 右邊 移動右邊索引//右邊 大於 左邊 移動左邊索引int maxArea = 0;int left = 0, right = height.size() - 1;int area = 0;while (left<right) { area = (height[left]<height[right] ? height[left] : height[right])*(right - left); maxArea = maxArea>area ? maxArea : area;if (height[left]>height[right]) right--;else left++; }return maxArea; }};

42. Trapping Rain Water

給定一非負的整數數組，數組的每個數字表示柱子的高度，如果把這些柱子組成一個容器，最多能盛多少水？

每個柱子(高度為h)所在的位置能夠裝的水的容量取決於它前面所有柱子的最高高度以及它後面所有柱子的最高高度，

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

代碼+注釋

class Solution {public: int trap(vector<int>& height) { //第一遍遍歷dp[i]中存入i位置左邊的最大值， //然後開始第二遍遍曆數組，第二次遍歷時找右邊最大值， //然後和左邊最大值比較取其中的較小值， //然後跟當前值A[i]相比，如果大於當前值，則將差值存入結果 int res = 0, mx = 0, n = height.size(); vector<int> dp(n, 0); for (int i = 0; i < n; ++i) { dp[i] = mx; mx = max(mx, height[i]); } mx = 0; for (int i = n - 1; i >= 0; --i) { dp[i] = min(dp[i], mx); mx = max(mx, height[i]); if (dp[i] > height[i]) res += dp[i] - height[i]; } return res; }};

推薦閱讀：