CodingTour —
ARTS #96

Algorithm

本周选择的算法题是：largest Rectangle in Histogram。

规则

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

img

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

img

Input: heights = [2,4]
Output: 4

Constraints:

  • 1 <= heights.length <= 105
  • 0 <= heights[i] <= 104

Solution

基于单调栈的解法：

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        ans, stack, heights = 0, [0], [0] + heights + [0]
        for i in range(len(heights)):
            while stack and heights[stack[-1]] > heights[i]:
                ans = max(ans, heights[stack.pop()] * (i - stack[-1] - 1))
            stack.append(i)
        return ans

Review

Flutter and Fuchsia. The next big thing?

一篇旧文，但观点暂时不过时。

我们可以试着想一想，Flutter 不仅仅是一个 framework，而是包含了一组工具集的 SDK，它可以将你的代码编译成 native 的机器码（无论是 iOS 还是 Android），所以从技术层面来讲，你现在写的 Flutter 代码是可以直接用在 Fuchsia 上的，同时 Google 是 Android、Flutter、Fuchsia 的拥有者（或许还应该算上 dart），Google 对 iOS 平台来说算第三方，但对 Android 来说至少也是二方，虽然 Flutter + Fuchsia 还处于早期阶段，但在未来真的有可能颠覆 Android 生态（或者打造一个新的生态）。

Tip

  • 依靠 App Store Connect API 实现了基于 TestFlight 的自助测试
  • 排查了一个线上服务调用失败的问题，最终发现是 NGINX 的某个配置有问题，学习了一次完整的排查流程

Share

2021 Q1 阅读记录。