题目:
思路:
我们可以安排俩个指针(数组下标)放在数组的头部和尾部;
每次移动高度较低的下标,判断是否为最大水量并记录;
(水量=下标差乘较小高度)
证明可行性:
如果移动高度较高的下标,由于下标差减小,故不论后面下标对应的高度增大,不变或减小都
会导致水量减小;
(增大:下标差减小,较小高度仍不变)
(不变:下标差减小,较小高度不变)
(减小:下标差减小,较小高度可能减小也可能不变)
如果移动高度较小的下标,当下一个下标对应高度增大时,水量便有可能增大;
!!!
对于高度较高的下标,可能存在另一高度与它组成最大水量,
如果移动便丢失了最大水量;
对于高度较低的下标,即便后面会出现更大的水量,但由于下标差的减小,新出现的最大水量
中的较低下标也不可能是原较低下标;
故我们可以放心移动高度较低的下标;
当俩高度一致时,如果有更大的水量出现,那么在俩高度之间必然存在至少俩个更高的高度,不管移动哪边只要我们接着使用高度较低移动原则任可遍历到
代码:
标签:11,减小,下标,高度,不变,水量,移动,LeetCode,贪心 From: https://blog.csdn.net/lyy_222/article/details/136995505