Python 刷Leetcode题库，顺带学英语单词（27）

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.   [#84]

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:
Input: [2,1,5,6,2,3]
Output: 10

题意：给定n个表示宽度为1的直方图之高度数组，求直方图中最大矩形的面积。

这题还是能用子序列推导式，子序列的最小值*宽度即面积：

>>> sub = lambda s:[s[i:j] for i in range(len(s)) for j in range(i+1,len(s)+1)]
>>> lst = [2,1,5,6,2,3]
>>> max([len(i)*min(i) for i in sublist(lst)])
10
>>> 
>>> lst = [2,1,3,5,2,3]
>>> max([len(i)*min(i) for i in sublist(lst)])
8
>>>

Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.  [#88]

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.

You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Constraints:
-10^9 <= nums1[i], nums2[i] <= 10^9
nums1.length == m + n
nums2.length == n

题意：合并已排序数组，把数组num2合并到num1中，假设num1有足够空间容纳num2

python是不用考虑空间够不够的，直接合并排序即可

1. >>> nums1 = [1,2,3,0,0,0]; m = 3;\
2.  nums2 = [2,5,6]; n = 3
3. >>> nums1 = sorted(nums1[:m]+nums2)
4. >>> nums1
5. [1, 2, 2, 3, 5, 6]
6. >>>

方法二：遍历数组，如果num2中的num1小则插入大则追加到num1

>>> def merge(n1,n2):
  for i in n2:
    for j,n in enumerate(n1):
      if i<=n:
        n1.insert(j,i)
        break
    else:
      n1.append(i)
  return n1
>>> nums1 = [1,2,3,0,0,0]; m = 3;\
  nums2 = [2,5,6]; n = 3
>>> 
>>> nums1 = nums1[:m]
>>> merge(nums1,nums2)
[1, 2, 2, 3, 5, 6]