从0开始刷算法题（leetcode数组篇）-- day04

1. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

真题点击此处：134.加油站

方法一：一次遍历
思路：最简单的能想到的解法就是从头到尾遍历每个加油站，并检查以该加油站为起点，最终能否行驶一周。但是我们可以通过减小被检查的加油站数目，来降低总的时间复杂度。

我们不妨思考一下，对于当前的加油站来说，当前加油站不是起始加油站，那么他到达当前加油站为止油箱里的剩余油量肯定是>=0的，为什么呢，很明显，如果小于0就不可能到达当前加油站了，所以我们可以得出一个结论，假设起始加油站为x,可以到达的最后一个加油站为y，（x<y），那么我们就可以知道从x出发最远能到达y，那么从x和y之间的任何一点出发最远也只是能到达y，因此我们在不能到达y+1的加油站时，直接从y+1进行继续判断就行。以下为代码实现：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        i,n=0,len(gas)
        while i<n:
            sum_gas,sum_cost=0,0
            cnt=0
            while cnt<n:
                j=(i+cnt)%n
                sum_gas+=gas[j]
                sum_cost+=cost[j]
                if sum_cost>sum_gas:
                    break
                cnt+=1
            if cnt==n:
                return i
            else:
                i=i+cnt+1

        return -1

时间复杂度：O（n），只进行了一次遍历。
空间复杂度：O（1），只使用了常量级的额外空间。

方法二：反向贪心遍历
思路：其实对于这题来说单纯判断能不能绕一圈其实直接判断所有的差值加起来是不是大于等于0就可以了，问题就是当可以绕一圈的时候如何确定起点的问题，我们可以采用反向遍历累加油量来计算最佳的起始位置，比如说我最后一个站的剩余油量也就是gas[i]-cost[i]为-2，也就意味我我还需要2升油才能到达第一个加油站，那么我们不妨假设在从后往前遍历的过程中出现第x个加油站的剩余油量为-1（这是x之后的所有差值累加的结果），是不是就意味着我从x出发是能到达最后一个加油站的，只不过不能到达第一个加油站而已，因此我们就可以知道：当出现剩余油量大于之前的剩余油量时就更新下标，表示当前位置是更优的起始位置。

以下为代码实现：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        sum_oil,index,max_oil=0,0,-float(inf)
        for i in range(len(gas)-1,-1,-1):
            sum_oil+=gas[i]-cost[i]
            if sum_oil>max_oil:
                max_oil=sum_oil
                index=i
        
        return index if sum_oil>=0 else -1 

时间复杂度：O（n），只进行了一次遍历。
空间复杂度：O（1），只使用了额外的常量级空间。

2. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

真题点击此处：11.盛最多水的容器

解题方法：双指针
思路：我们可以初始化左指针left指向第一个下标，右指针指向最后一个下标，因为在这种情况下的距离是最大的，然后我们就计算当前能装水的体积（水的容量：两个指针之间的较小值 * 两个指针之间的距离），在我们移动左右指针的时候距离是肯定的会减小的，所以问题就变成了移动左指针还是右指针的问题，显而易见，我们肯定是移动较小的指针得到的解法是更优的。

以下为代码实现：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left,right,max_water=0,len(height)-1,0
        while left!=right:
            water=min(height[left],height[right]) * (right-left)
            max_water=max(max_water,water)

            if height[left]<height[right]:
                left+=1
            else:
                right-=1

        return max_water

时间复杂度：O（n）,只进行了一次遍历。
空间复杂度：O（1），只使用了常量级的额外空间。

3.下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

真题点击此处：31.下一个排列

解题方法：两次遍历

思路：我们想要找到一个比当前大的序列，并且这个序列变大的幅度尽可能小，因此，可以有：

1. 我们需要将一个左边的较小数与一个右边的较大数交换，以能够让当前排列变大，从而得到下一个排列。

2. 同时我们要让这个较小数尽量靠右，而较大数尽可能小。当交换完成后，原来的较小数的位置的右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。

那我们该如何找到这个尽量靠右的较小数和尽可能小的较大数呢？我们从后往前遍历，当出现nums[i]<nums[i+1]时，nums[i]即为较小数，而此时nums[i+1]以及它以后的数字都是降序排序的，接下来我们再从后往前遍历，找到第一个nums[j]>nums[i],此时nums[j]即为较大数，此时直接交换nums[i]和nums[j]，由于nums[i+1]之后的数字都是降序的，因此我们直接通过双指针交换首尾的值，即可实现降序操作。

以下为代码实现：

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        i=len(nums)-2
        while i>=0 and nums[i]>=nums[i+1]:
            i-=1
        if i>=0:
            j=len(nums)-1
            while j>=0 and nums[j]<=nums[i]:
                j-=1
            nums[i],nums[j]=nums[j],nums[i]

        left,right=i+1,len(nums)-1
        while left<right:
            nums[left],nums[right]=nums[right],nums[left]
            left+=1
            right-=1

时间复杂度：O（n），最多进行两次遍历。
空间复杂度：O（1），原地修改数组，只使用了个别变量。