首页 > 代码库 > LeetCode "Container With Most Water" - GREEDY?
LeetCode "Container With Most Water" - GREEDY?
O(n^2) is a naive solution. As rule of thumb, there must be O(n) soluion. Yes - Greedy.
We assume widest container contains the most water, greedily, but it is possible that we have higher heights with narrower range, so we proceed. Of course we disgard lower heights when shrinking window - we are greedy.
class Solution {public: int maxArea(vector<int> &height) { size_t cnt = height.size(); int i = 0, j = cnt - 1; int maxWater = std::numeric_limits<int>::min(); while (i < j) { int minH = std::min(height[i], height[j]); maxWater = std::max(maxWater, minH * (j - i)); if (height[i] <= height[j]) while (height[++i] < minH && i < j); else while (height[j--] < minH && i < j); } return maxWater; }};
As shown above, I did another small optimization: when window gets shrinked, we can skip all even-shorter heights.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。