LeetCode 11 Container With Most Water

Online Judge

问题描述

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.
以n条以(i, ai)和(i, 0)为端点的线段中找出两条，使得这两条线段和x轴构成的容器所能装下的水最多。

问题分析与思路

  装水的容量，实际就是求两个线段中最短的线段长度乘以线段之间的距离。
  最简单最暴力的方法就是把每两个线段都拿出来进行计算装水的容量，然而这会使得计算量很大，超出了程序的时间限制。
  容积即面积，它受长和高的影响，当长度减小时候，高必须增长才有可能提升面积，所以我们从长度最长时开始递减，然后寻找更高的线来更新候补。

问题求解

  C++的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
	int maxArea(vector<int>& height) {
		int maxArea = INT_MIN;
		int head = 0, tail = height.size() - 1;
		while (head < tail) {
			int area = (height[head] < height[tail] ? height[head] : height[tail]) * (tail - head);
			if (area > maxArea)	maxArea = area;
			if (height[head] <= height[tail]) {
				head++;
			}
			else {
				tail--;
			}
		}
		return maxArea;
	}
};

相关知识点总结

条件操作符 ?:

  条件操作符?:是一个三目操作符，其格式为cond?expr1 : expr2;
  含义为如果cond的值为true或者非零，则运算结果为expr1，否则为expr2。

INT_MIN INT_MAX

  在标准头文件limits.h中定义如下：

1
2
#define INT_MAX 2147483647  
#define INT_MIN (-INT_MAX - 1)

  这里没有简单地将INT_MIN赋值成-2147483647，是因为-2147483648对于编译器而言是个表达式，而2147483648对于32-bit整数是无法表示的，所以经过这个表达式的结果是未定义的。在GCC上直接写-2147483648后，编译器给出了警告，说结果是unsigned。
  更多的关于INT_MIN的探讨可以参见这里的博客.

啰嗦几句

  一个暑假都没有更新博客了，现在回到了学校才开始继续更新，做一些自己想做的事情。做做题看看书感觉生活很简单而美好。
  最近几天在刷口译考试的题，感觉自己不一定能过了，做题的速度太慢了，50min6篇阅读理解，我有点hold不住，但是还是会去考的，但愿能过吧。