1. 柱状图中最大的矩形
难度：困难
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
代码：
class Solution(object): def largestRectangleArea(self, heights): """ :type heights: List[int] :rtype: int """ largest_rectangle = 0 ls = len(heights) stack = [-1] top, pos = 0, 0 for pos in range(ls): while top > 0 and heights[stack[top]] > heights[pos]: largest_rectangle = max(largest_rectangle, heights[stack[top]] * (pos - stack[top - 1] - 1)) top -= 1 stack.pop() stack.append(pos) top += 1 while top > 0: largest_rectangle = max(largest_rectangle, heights[stack[top]] * (ls - stack[top - 1] - 1)) top -= 1 return largest_rectangle if __name__ == "__main__": s = Solution() print (s.largestRectangleArea([2,1,5,6,2,3]))
输出：
10
2. 汇总区间
难度：简单
给定一个无重复元素的有序整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
"a->b" ，如果 a != b
"a" ，如果 a == b
示例 1：
输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
示例 2：
输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
示例 3：
输入：nums = []
输出：[]
示例 4：
输入：nums = [-1]
输出：["-1"]
示例 5：
输入：nums = [0]
输出：["0"]
提示：
0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同
nums 按升序排列
代码：
class Solution: def summaryRanges(self, nums) : n = len(nums) left = 0 right = 0 ans = [] while right < n: while right < n - 1 and nums[right] + 1 == nums[right + 1]: right += 1 tmp = [str(nums[left])] if nums[left] != nums[right]: tmp.append("->") tmp.append(str(nums[right])) ans.append("".join(tmp)) right += 1 left = right return ans if __name__ == "__main__": s = Solution() print(s.summaryRanges([0,1,2,4,5,7])) print(s.summaryRanges([0,2,3,4,6,8,9])) print(s.summaryRanges([])) print(s.summaryRanges([-1])) print(s.summaryRanges([0]))
输出：
['0->2', '4->5', '7']
['0', '2->4', '6', '8->9']
[]
['-1']
['0']
3. 寻找旋转排序数组中的最小值
难度：中等
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
代码：
class Solution(object): def findMin(self, nums): flag = True if nums[0] < nums[-1]: flag = True else: flag = False for i in range(1, len(nums)): if flag: if nums[i] < nums[i - 1]: return nums[i] else: if nums[len(nums) - i] < nums[len(nums) - 1 - i]: return nums[len(nums) - i] return nums[0] if __name__ == "__main__": s = Solution() print(s.findMin([3,4,5,1,2])) print(s.findMin([4,5,6,7,0,1,2])) print(s.findMin([11,13,15,17]))
输出：
1
0
11
