Algorithm做算法題，Review點評英文文章，Tip總結(jié)技術(shù)技巧，Share做技術(shù)分享。每周打卡一次，這就是ARTS打卡。

1. 做算法題

leetcode第11題. 盛最多水的容器

題目:給你 n 個非負(fù)整數(shù) a1，a2，...，an，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。說明：你不能傾斜容器，且 n 的值至少為 2。

示例

圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。

示例：

輸入：[1,8,6,2,5,4,8,3,7]
輸出：49

解題思路：題目是要求找到柱子（垂直線）形成的容器中最大的那個，容器的容水量等于兩個柱子中最短的柱高乘以兩柱子的距離。最簡單的方法是窮舉出所有柱子形成的容器計算容水量，找到最大的。遍歷任意兩個柱子的時間復(fù)雜度O(n^{2)，再找出最大的容器時間復(fù)雜度O(n)，總共時間復(fù)雜度O(n}3)。沒有增加額外空間，空間復(fù)雜度O(1)。這顯然是無法忍受的。

有什么辦法能減少遍歷次數(shù)呢？從容器水量計算來看，有兩個變量，兩柱最短的高度和兩柱的距離?？刂埔粋€變量，兩柱的距離。這個距離當(dāng)然越大容器水量就越大，假設(shè)初始狀態(tài)是首尾兩個柱子，距離最大，計算出水容量。再改變這個變量，左右柱子進行移動，找到更大的水容量。怎么移動呢？將兩柱中較短的那跟移向中間，才可能是的水容量變大。因為移動較長的那跟柱子的話，兩柱距離縮小了，即使移動后的柱子更高但還是受限于之前的短柱子，水容量一定是減少的。只有移動較短的柱子才有可能找到更大的容器。這樣遍歷只需要一遍，時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

解題代碼：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r, max_area = 0, len(height)-1, 0
        while l < r:
            max_area = max(max_area, (r - l) * min(height[l], height[r]))
            if height[r] < height[l]:
                r -= 1
            else:
                l += 1
        return max_area

2.點評英文文章

使用logstash工具配置過程中要參考官方文檔，英文的技術(shù)手冊看起來雖然慢點，但邏輯還算是比較清楚。在邏輯復(fù)雜的地方，給出案例，這無疑是一劑良方。例如下面這段描述：

The pattern should match what you believe to be an indicator that the field is part of a multi-line event.

The what must be previous or next and indicates the relation to the multi-line event.

The negate can be true or false (defaults to false). If true, a message not matching the pattern will constitute a match of the multiline filter and the what will be applied. (vice-versa is also true)

初看上去非常繞，正則、前后、真假？什么東西??！再看看下面的例子就好理解多了，

Another example is to merge lines not starting with a date up to the previous line..

 input {
   file {
     path => "/var/log/someapp.log"
     codec => multiline {
       # Grok pattern names are valid! :)
       pattern => "^%{TIMESTAMP_ISO8601} "
       negate => true
       what => "previous"
     }
   }
 }

This says that any line not starting with a timestamp should be merged with the previous line.

3. 技術(shù)技巧

用vmware跑Linux虛擬機是很常見的操作，那么你是如何把宿主機中的文件拷貝到虛擬機中呢？如果linux是圖形界面，直接拖拽即可。但如果是命令行界面怎么辦。可以通過優(yōu)盤掛載到Linux中，實現(xiàn)文件轉(zhuǎn)移，不過有些麻煩。既然虛擬機可以看作是一臺獨立的計算機，網(wǎng)絡(luò)是通的就可以用xftp工具傳輸文件，也可以通過xshell工具連接虛擬機。

4. 技術(shù)分享

不管是公司服務(wù)器運維還是自搭云主機，經(jīng)常要登入看看磁盤、CPU、內(nèi)存和進程運行情況。用logstash+shell實現(xiàn)自動監(jiān)控并發(fā)郵件報告，具體參考我寫在github的文章。