题解
题目描述
S中最大的连续子序列矩形面积。连续子序列s的矩形面积定义：min{s[i]|0<i<=len(s)} * len(s)。如：S=[2,1,5,6,2,3]，最大的连续子序列矩形面积为10，此连续子序列s=[5,6]。 题解
遍历所有连续子序列并计算其矩形面积，而后取最大值即可。时间复杂度为O(n^2)，空间复杂度为O(1)。但存在重复计算，可对此部分进行优化。转化成另一种形式的遍历：对每个可能的min{s[i]|0<i<=len(s)}进行遍历。而后取此时满足条件的最大len(s)即可。前者即序列的每个取值S[i](0<i<=len(S))，最大len(s)=Right - Left - 1。Right满足(S[Right] < S[i] && Right > i)，Left满足(S[Left] < S[i] && Left < i)。设置标兵：S[0] = S[len(S) + 1] = min{S[i]|0<i<=len(S)} - 1。利用栈保存状态，时间复杂度为O(n)，空间复杂度为O(n)。
代码
typedef unsigned int uint;static const uint MAX_SIZE = 0x8000;static uint keep[MAX_SIZE];class Solution {public: int largestRectangleArea(vector & heights) { size_t len = heights.size(), keepEnd = 0, rect = 0; for (keep[0] = len; len--; keep[++keepEnd] = len) { uint tmp = heights[len], pos = keep[keepEnd]; while (keepEnd) { uint area = heights[pos]; if (tmp >= area) break; pos = keep[--keepEnd]; if ((area *= (pos - len - 1U)) > rect) rect = area; } } while (keepEnd) { uint area = heights[keep[keepEnd]]; if ((area *= keep[--keepEnd]) > rect) rect = area; } return rect; }}; 总结
主要应用了等价转化的思想。