/**

11.盛最多水的容器

题目

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：

输入：height = [1,1]
输出：1
示例 3：

输入：height = [4,3,2,1,4]
输出：16
示例 4：

输入：height = [1,2,1]
输出：2

提示：

n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

测试代码

print(maxArea([1,8,6,2,5,4,8,3,7]))

笔记

这道题就是经典的双指针题目了
思路就是两边往中间移
那边小就移动哪一边
每次都获取当前的容量
然后就可以获得最大容量了

代码地址

https://github.com/zmfflying/ZMathCode
*/

解题代码

import Foundation

func maxArea(_ height: [Int]) -> Int {
    var maxArea: Int = 0
    
    //从两边往中间移
    var left: Int = 0
    var right: Int = height.count - 1
    
    while left < right {
        let leftHeight: Int = height[left]
        let rightHeight: Int = height[right]
        
        //得到当前容量
        let area: Int = min(leftHeight, rightHeight) * (right - left)
        //判断最大容量
        maxArea = max(maxArea, area)
        
        //哪边元素比较小就移动哪一边
        if leftHeight < rightHeight  {
            left += 1
        } else {
            right -= 1
        }
    }
     
    return maxArea
}

/**

26.删除排序数组中的重复项

题目

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

测试代码

var nums = [0,0,1,1,1,2,2,3,3,4]
print(removeDuplicates(&nums), nums)

笔记

这道题是要使用快慢指针的思想
因为题目要求只要前面数据正确就可以,而且还是有序数组
那么就可以创建快慢指针
慢指针指向第 0 个元素
快指针指向第 1 个元素

然后在快指针往后移动的过程中
当快指针指向的元素和慢指针指向的元素不相等的时候移动慢指针即可

代码地址

https://github.com/zmfflying/ZMathCode
*/

解题代码

import Foundation

func removeDuplicates(_ nums: inout [Int]) -> Int {
    if nums.count == 0 {
        return 0
    }
    //快慢指针
    var slow = 0
    var fast = 1
    while fast < nums.count {
        //当两个指针指向的元素不相等的时候慢指针才移动
        if nums[slow] != nums[fast] {
            slow += 1
            nums[slow] = nums[fast]
        }
        //否则就是快指针移动
        fast += 1
    }
    return slow + 1
}

/**

283.移动零

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

测试代码

var nums = [0,1,0,3,12]
moveZeroes(&nums)
print(nums)

笔记

这道题就是也是双指针
维护两段数据的正确:
0 < left 一定是非0
left <= right 一定是0

具体方法就是
循环的时候,遇见非0元素就左右都移动
同时进行元素交换
遇见0的时候只移动右边

代码地址

https://github.com/zmfflying/ZMathCode
*/

解题代码

import Foundation

func moveZeroes(_ nums: inout [Int]) {
    if nums.count <= 1 {
        return
    }
    //0 < left 一定是非0
    //left <= right 一定是0
    var left = 0
    var right = 0
    while right < nums.count {
        //right 非0的时候 左右都要移动
        //还要交换 right 和 left的值
        if nums[right] != 0 {
            if left != right {
//                let temp = nums[left]
//                nums[left] = nums[right]
//                nums[right] = temp
                
                // left != right 的时候 nums[left] 一定为0
                nums[left] = nums[right]
                nums[right] = 0
            }
            
            left += 1
        }
        //right 为0的时候, 只移动右边
        right += 1
    }
}