数形结合

数形结合是数学上一类重要的思想方法，通过将问题图形化，往往能对问题产生更加直观的理解

实际上，在计算机的算法问题上，利用数形结合将问题直观化，在某些情况下更方便我们找到解决问题的要点

线性问题的数形结合

一般涉及到数组、顺序、逆序的线性问题，可通过画折线将问题直观化

例1（leetcode 122）

给定一个数组，它的第 i 个元素是一支给定股票在第 i 天的价格。
对该股票进行若干次买卖，设计一个算法来计算所能获取的最大利润。

以数组[7,1,5,3,6,4]为例，要达到获利，大小关系的判断肯定跑不掉，画图看一下：

股票走势
通过线条可以直观地看到，股票走势形成了波峰和波谷，要实现利润最大化，必然需要在每个波谷买入，并在接下来的波峰卖出。换句话说，就是计算上图上升线条的长度总和

那么：

class Solution(object):
    def maxProfit(self, prices):
        max_money = 0
        for i in range(len(prices)-1):
            if prices[i] < prices[i+1]:
                max_money += (prices[i+1] - prices[i])
        return max_money

例2 下一个排列（leetcode 31）

将给定数字序列重新排列成字典序中下一个更大的排列
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）

以[3,4,5,7,6,3]为例，下一个序列应该是[3,4,6,3,5,7]
直觉上这个问题肯定涉及到判断大小关系然后进行位置调整的，先画个图

[3,4,5,7,6,3]
要恰好得到字典序中下一个更大的排列，必然要从序列的右侧开始调整。我们要做的，就是找到调整的方法

观察上图，从右侧开始看，如果从右至左是升序的，则不可调换这段升序序列中的任2个数（因为如果调换，形成的排列会更小），例如3-6-7这段不能动。直到从右至左找到一个降序的序列（也就是波峰），只需要把这个序列的2个数换位置，就可以得到更大的排列，如交换5和7，得到更大的[3,4,7,5,6,3]

但显然这个序列过大了，[3,4,6,3,5,7]才是符合要求的序列。因为5需要被更大的数替换，因此先把5所在位置叫做交换入口，实际上交换入口就是波峰左侧第一个位置。可以发现，[3,4,6,3,5,7]中，数字6代替了5的位子。没错，我们需要把波峰右侧所有比5大的数中最小的一个与5互换位置，而不能直接将入口值与波峰值交换，以避免过度变大序列。同时，在交换完成后，将交换入口后的序列升序排列，即排序形成3-5-7，保证形成的序列恰为下一个更大的序列

实现代码如下：

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l = len(nums)
        # 如果只有一个数或者为空，直接返回
        if l == 1 or l == 0:
            return nums
        # 如果数字序列多于2个数
        else:
            # 从右向左扫描第一个波峰位置
            right = l - 1
            left = right - 1
            while left >= 0:
                if nums[left] < nums[right]:
                    # 找到波峰后，定位数字交换的入口，pop后面最小的数并将其插入到入口位置
                    repalce_index = right
                    for index in range(right+1, l):
                        if nums[index] > nums[left] and nums[index] < nums[repalce_index]:
                            repalce_index = index
                    nums.insert(left, nums.pop(repalce_index))
                    # 插入位置的后面需要升序排列
                    begin = left + 1
                    for end in range(l-1, left+1, -1):                      
                        for _ in range(begin, end):
                            index_next = _+1
                            if nums[_] > nums[index_next]:
                                temp = nums[_]
                                nums[_] = nums[index_next]
                                nums[index_next] = temp  
                    return nums
                else:
                    right -= 1
                    left = right - 1                      
            # 如果跳出了上面的while循环，说明需要将数字重新排列成最小的排列
            left = 0
            right = l - 1
            while left < right:
                    temp = nums[right]
                    nums[right] = nums[left]
                    nums[left] = temp
                    left += 1
                    right -= 1
            return nums